Finding geometric representations of apex graphs is NP-hard
From MaRDI portal
Publication:2154093
DOI10.1007/978-3-030-96731-4_14OpenAlexW3153542555MaRDI QIDQ2154093
Kshitij Gajjar, Dibyayan Chakraborty
Publication date: 13 July 2022
Full work available at URL: https://arxiv.org/abs/2104.09976
VLSI designplanar graphrecognition problemHamiltonian pathapex graphgeometric intersection graph\( \mathsf{NP} \)-hard1-STRINGPURE-2-DIR
Related Items (2)
Finding geometric representations of apex graphs is \textsf{NP}-hard ⋮ Recognizing geometric intersection graphs stabbed by a line
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fast partitioning \(l\)-apex graphs with applications to approximating maximum induced-subgraph problems
- Graph minors. XX: Wagner's conjecture
- Interval representations of planar graphs
- String graphs. II: Recognizing string graphs is NP-hard
- The book thickness of a graph
- On grid intersection graphs
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Label placement by maximum independent set in rectangles
- A special planar satisfiability problem and a consequence of its NP- completeness
- Intersection graphs of segments
- Unit disk graph recognition is NP-hard
- Combinatorial algorithms. 31st international workshop, IWOCA 2020, Bordeaux, France, June 8--10, 2020, Proceedings
- 3-colorable planar graphs have an intersection segment representation using 3 slopes
- Planar graphs have 1-string representations
- Recognizing Weighted Disk Contact Graphs
- Realization of Simply Connected Polygonal Linkages and Recognition of Unit Disk Contact Trees
- Characterizations of Deque and Queue Graphs
- Fast and accurate algorithms for protein side-chain packing
- Geometric Intersection Graphs: Do Short Cycles Help?
- Not all planar graphs are in PURE-4-DIR
- Every planar graph is the intersection graph of segments in the plane
- Bend-Bounded Path Intersection Graphs: Sausages, Noodles, and Waffles on a Grill
- Homothetic triangle representations of planar graphs
- Topology of Thin Film RC Circuits
- ON CONVEX POLYHEDRA IN LOBAČEVSKIĬ SPACES
- Recognizing string graphs in NP
This page was built for publication: Finding geometric representations of apex graphs is NP-hard
