Classes and recognition of curve contact graphs

DOI10.1006/jctb.1998.1846zbMath0943.05069OpenAlexW2034335672MaRDI QIDQ1272471

Petr Hliněný

Publication date: 5 September 2000

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/690266bc896dabbf8f3660907df126962940ebd6

zbMATH Keywords

recognitioncontact graphs

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75)

Related Items (13)

CPG graphs: some structural and hardness results ⋮ Contact Graphs of Circular Arcs ⋮ Unit disk representations of embedded trees, outerplanar and multi-legged graphs ⋮ The maximal clique and colourability of curve contact graphs ⋮ Crossing edge minimization in radial outerplanar layered graphs using segment paths ⋮ Characterising circular-arc contact \(B_0\)-VPG graphs ⋮ Low Ply Drawings of Trees ⋮ Optimal polygonal representation of planar graphs ⋮ On contact graphs of paths on a grid ⋮ Using graph concepts to assess the feasibility of a sequenced air traffic flow with low conflict rate ⋮ Coloring non-crossing strings ⋮ On some special classes of contact \(B_0\)-VPG graphs ⋮ Topological inductive constructions for tight surface graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A unified approach to visibility representations of planar graphs
• String graphs. II: Recognizing string graphs is NP-hard
• Reducing prime graphs and recognizing circle graphs
• String graphs requiring exponential representations
• Intersection graphs of curves in the plane
• Intersection graphs of segments
• The complexity of induced minors and related problems
• The maximal clique and colourability of curve contact graphs
• Representation of a finite graph by a set of intervals on the real line
• On Triangle Contact Graphs

This page was built for publication: Classes and recognition of curve contact graphs