Contact Representations of Planar Graphs: Extending a Partial Representation is Hard

DOI10.1007/978-3-319-12340-0_12zbMath1417.05133OpenAlexW945065150MaRDI QIDQ2945185

Steven Chaplick, Paul Dorbec, Juraj Stacho, Mickaël Montassier, Jan Kratochvíl

Publication date: 9 September 2015

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-12340-0_12

Mathematics Subject Classification ID

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

Related Items (19)

Simple algorithms for partial and simultaneous rectangular duals with given contact orientations ⋮ Extending Partial Orthogonal Drawings ⋮ Extending partial representations of interval graphs ⋮ Minimal Obstructions for Partial Representations of Interval Graphs ⋮ Extending partial representations of circular-arc graphs ⋮ Partial and simultaneous transitive orientations via modular decompositions ⋮ Extending partial representations of rectangular duals with given contact orientations ⋮ Colored anchored visibility representations in 2D and 3D space ⋮ Stick graphs with length constraints ⋮ Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. Chapter I: theory ⋮ Recognizing Stick Graphs with and without Length Constraints ⋮ Minimal obstructions for partial representations of interval graphs ⋮ On the classes of interval graphs of limited nesting and count of lengths ⋮ Extending upward planar graph drawings ⋮ Extending partial representations of proper and unit interval graphs ⋮ Unnamed Item ⋮ The partial visibility representation extension problem ⋮ Inserting one edge into a simple drawing is hard ⋮ Extending Partial Orthogonal Drawings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Extending partial representations of proper and unit interval graphs
• A polynomial time circle packing algorithm
• Reducing prime graphs and recognizing circle graphs
• On grid intersection graphs
• The complexity of induced minors and related problems
• Extending partial representations of interval graphs
• Extending Partial Representations of Circle Graphs
• Extending Partial Representations of Function Graphs and Permutation Graphs
• Complexity of Some Geometric and Topological Problems
• Hierarchies and planarity theory
• An Efficient Test for Circular-Arc Graphs
• Algorithms on circular-arc graphs
• Topics in Intersection Graph Theory
• Graph Classes: A Survey
• On Triangle Contact Graphs
• NP completeness of the edge precoloring extension problem on bipartite graphs
• Extending Partial Representations of Subclasses of Chordal Graphs
• NP‐completeness of list coloring and precoloring extension on the edges of planar graphs
• Partial orders of dimension 2
• A Characterization of Comparability Graphs and of Interval Graphs

This page was built for publication: Contact Representations of Planar Graphs: Extending a Partial Representation is Hard