Finding geometric representations of apex graphs is \textsf{NP}-hard
From MaRDI portal
Publication:6175518
DOI10.1016/j.tcs.2023.114064MaRDI QIDQ6175518
Kshitij Gajjar, Dibyayan Chakraborty
Publication date: 18 August 2023
Published in: Theoretical Computer Science (Search for Journal in Brave)
VLSI designplanar graphrecognition problemHamiltonian pathapex graphgeometric intersection graph\textsc{1-String}\textsc{Pure-2-Dir}\textsf{NP}-hard
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
- On bounding the chromatic number of L-graphs
- Simple \(k\)-planar graphs are simple \((k + 1)\)-quasiplanar
- Finding geometric representations of apex graphs is NP-hard
- 3-colorable planar graphs have an intersection segment representation using 3 slopes
- Planar graphs have 1-string representations
- Über eine Eigenschaft der ebenen Komplexe
- Characterizations of Deque and Queue Graphs
- Fast and accurate algorithms for protein side-chain packing
- Geometric Intersection Graphs: Do Short Cycles Help?
- Crossing Numbers of Graphs
- 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
- Parameterized Algorithms
- ON CONVEX POLYHEDRA IN LOBAČEVSKIĬ SPACES
This page was built for publication: Finding geometric representations of apex graphs is \textsf{NP}-hard
