Open Research Index

Deciding monotonicity of simple drawings of the complete graph

Oswin Aichholzer, Thomas Hackl, Alexander Pilz, Gelasio Salazar, Birgit Vogtenhuber

arXivarxiv/2607.06240Jul 7, 2026cs.CGscore 0

A drawing of a graph is {\em $x$-monotone} if every vertical line intersects each edge of the graph at most once. We present an $O(n^5)$ time algorithm for deciding whether a simple drawing of the complete graph $K_n$ is weakly isomorphic to an $x$-monotone drawing. We note that this algorithm can also decide whether a drawing of $K_n$ is strongly isomorphic to an $x$-monotone drawing.

SourceJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2607.06240
curl -X POST /api/v1/records/arxiv/2607.06240/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.06240/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'