Contact representations of planar graphs: extending a partial representation is hard
From MaRDI portal
Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Recommendations
Cites work
- A Characterization of Comparability Graphs and of Interval Graphs
- A polynomial time circle packing algorithm
- Algorithms on circular-arc graphs
- An Efficient Test for Circular-Arc Graphs
- Complexity of some geometric and topological problems
- Extending partial representations of circle graphs
- Extending partial representations of function graphs and permutation graphs
- Extending Partial Representations of Subclasses of Chordal Graphs
- Graph Classes: A Survey
- Hierarchies and planarity theory
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 739017 (Why is no real title available?)
- NP completeness of the edge precoloring extension problem on bipartite graphs
- NP‐completeness of list coloring and precoloring extension on the edges of planar graphs
- On grid intersection graphs
- On Triangle Contact Graphs
- Partial orders of dimension 2
- Reducing prime graphs and recognizing circle graphs
- Testing planarity of partially embedded graphs
- The complexity of induced minors and related problems
- Topics in Intersection Graph Theory
Cited in
(22)- On the classes of interval graphs of limited nesting and count of lengths
- On contact representations of directed planar graphs
- Simple algorithms for partial and simultaneous rectangular duals with given contact orientations
- Colored anchored visibility representations in 2D and 3D space
- Stick graphs with length constraints
- Extending partial representations of rectangular duals with given contact orientations
- Minimal obstructions for partial representations of interval graphs
- Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. I: Theory
- Extending Partial Orthogonal Drawings
- Extending partial orthogonal drawings
- scientific article; zbMATH DE number 7559402 (Why is no real title available?)
- Square-contact representations of partial 2-trees and triconnected simply-nested graphs
- Recognizing stick graphs with and without length constraints
- Proportional Contact Representations of Planar Graphs
- Inserting one edge into a simple drawing is hard
- Contact graphs of line segments are NP-complete
- Extending partial representations of circular-arc graphs
- Partial and simultaneous transitive orientations via modular decompositions
- Minimal obstructions for partial representations of interval graphs
- Extending partial 1-planar drawings
- Simultaneous contact representations of planar graphs
- Partial and constrained level planarity
This page was built for publication: Contact representations of planar graphs: extending a partial representation is hard
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2945185)
