The Complexity of Several Realizability Problems for Abstract Topological Graphs

DOI10.1007/978-3-540-77537-9_16MaRDI QIDQ5452218zbMATHOpenAlexFDO

Authors Jan Kynčl

Publication date 25 March 2008

Published in Graph Drawing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-77537-9_16

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)

Recommendations

• Simple realizability of complete abstract topological graphs in P
• Simple realizability of complete abstract topological graphs simplified
• Simple realizability of complete abstract topological graphs simplified
• scientific article; zbMATH DE number 7030516
• On rectilinear topological graphs

Cites work

• scientific article; zbMATH DE number 434700 (Why is no real title available?)
• scientific article; zbMATH DE number 2079388 (Why is no real title available?)
• A linear-time algorithm for drawing a planar graph on a grid
• A special planar satisfiability problem and a consequence of its NP- completeness
• Decidability of string graphs
• Enumeration of simple complete topological graphs
• Graph Drawing
• Graph Drawing
• Noncrossing Subgraphs in Topological Layouts
• On the crossing number of complete graphs
• Recognizing string graphs in NP
• Recognizing string graphs is decidable
• Relations Between Crossing Numbers of Complete and Complete Bipartite Graphs
• Simultaneous Graph Embeddings with Fixed Edges
• String graphs requiring exponential representations
• String graphs. I: The number of critical nonstring graphs is infinite
• String graphs. II: Recognizing string graphs is NP-hard
• Unavoidable configurations in complete topological graphs

Cited in

(6)

• Simple realizability of complete abstract topological graphs simplified
• On rectilinear topological graphs
• Simple realizability of complete abstract topological graphs in P
• On the realisability of double-cross matrices by polylines in the plane
• Recent advances in exact crossing minimization (extended abstract)
• Simple realizability of complete abstract topological graphs simplified

This page was built for publication: The Complexity of Several Realizability Problems for Abstract Topological Graphs

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