Finding geometric representations of apex graphs is NP-hard

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

zbMATH Keywords

VLSI designplanar graphrecognition problemHamiltonian pathapex graphgeometric intersection graph\( \mathsf{NP} \)-hard1-STRINGPURE-2-DIR

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

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