Simple realizability of complete abstract topological graphs simplified

DOI10.1007/978-3-319-27261-0_26MaRDI QIDQ2959766zbMATH OpenOpenAlexFDO

Authors Jan Kynčl

Publication date 10 February 2017

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1608.05867

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Abstract: An abstract topological graph (briefly an AT-graph) is a pair $A=(G,mathcalX)$ where $G=(V,E)$ is a graph and $mathcalXsubseteqEchoose2$ is a set of pairs of its edges. The AT-graph $A$ is simply realizable if $G$ can be drawn in the plane so that each pair of edges from $mathcalX$ crosses exactly once and no other pair crosses. We show that simply realizable complete AT-graphs are characterized by a finite set of forbidden AT-subgraphs, each with at most six vertices. This implies a straightforward polynomial algorithm for testing simple realizability of complete AT-graphs, which simplifies a previous algorithm by the author. We also show an analogous result for independent $mathbb{Z}_2$-realizability, where only the parity of the number of crossings for each pair of independent edges is specified.

Recommendations

• Simple realizability of complete abstract topological graphs simplified
• Simple realizability of complete abstract topological graphs in P
• The Complexity of Several Realizability Problems for Abstract Topological Graphs
• scientific article; zbMATH DE number 7030516
• Saturated simple and \(k\)-simple topological graphs

Cited in

(10)

• Simple realizability of complete abstract topological graphs simplified
• Extending simple drawings
• Topological Drawings of Complete Bipartite Graphs
• Quantitative restrictions on crossing patterns
• On the Maximum Number of Crossings in Star-Simple Drawings of K_n with No Empty Lens
• Closing in on Hill's conjecture
• An optimal algorithm for reconstructing point set order types from radial orderings
• The Complexity of Several Realizability Problems for Abstract Topological Graphs
• Simple realizability of complete abstract topological graphs in P
• Separable drawings: extendability and crossing-free Hamiltonian cycles

This page was built for publication: Simple realizability of complete abstract topological graphs simplified

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2959766)