Skip to content
DraconiticResearch
Search Sources API
194,161 studies31 sourcesUpdated 47 min ago
Peer-reviewedCC BYJournal of Computational Geometry

Deciding monotonicity of simple drawings of the complete graph

  • Oswin Aichholzer1
  • Gelasio Salazar2
  • Birgit Vogtenhumber1
  1. 1Graz University of Technology
  2. 2Universidad Autonoma de San Luis Potosi
Read full textDOICite

Abstract

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

Related

  1. Realizing graph automorphisms as geometric symmetries of straight line drawings
    Saul D. Freedman, Melissa Lee, Dragan Marušič +1
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv
  2. Deciding lettericity is NP-complete, even for four-colorable comparability graphs
    Vincent Vatter
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Endpoint Absolute Monotonicity for the Complete Elliptic Integral of the First Kind
    Qintao Deng, Yunjia Kou, Fulin Zhong
    arXivPreprintarXiv licenceFull textAnalysis & PDEsarXiv
  4. Complete Monotonicity of the Srivastava-Tomovski Function and Its Laplace-Wright Realization: Necessary and Sufficient Conditions
    Rey R. Cuenca, Welfredo R. Patungan, Ruzzel Ragas
    arXivPreprintarXiv licenceFull textProbabilityStatisticsarXiv
  5. DistFlow and Its Conic Relaxation: Regularity, Monotonicity, and Hybrid Exactness via Graph Decomposition
    Xinliang Dai
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv

Cite

BibTeXRIS
BibTeX
@article{aichholzer2026deciding,
  title = {{Deciding monotonicity of simple drawings of the complete graph}},
  author = {Oswin Aichholzer and Gelasio Salazar and Birgit Vogtenhumber},
  journal = {Journal of Computational Geometry},
  year = {2026},
  month = oct,
  doi = {10.20382/jocg.v17i1a11},
  url = {https://doi.org/10.20382/jocg.v17i1a11},
  note = {CC BY},
}
RIS
TY  - JOUR
TI  - Deciding monotonicity of simple drawings of the complete graph
AU  - Oswin Aichholzer
AU  - Gelasio Salazar
AU  - Birgit Vogtenhumber
PY  - 2026
DA  - 2026/10/29
JO  - Journal of Computational Geometry
DO  - 10.20382/jocg.v17i1a11
UR  - https://doi.org/10.20382/jocg.v17i1a11
AB  - A drawing of a graph is 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.
SN  - 1920-180X
ER  -