Segment representations with small resolution

DOI10.1016/j.ipl.2019.105868zbMath1481.05113arXiv1810.07072OpenAlexW2980670821MaRDI QIDQ2338214

Therese C. Biedl

Publication date: 21 November 2019

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1810.07072

zbMATH Keywords

intersection graphplanar graphresolutioncomputational geometrysegment representation

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• Unnamed Item
• String graphs. II: Recognizing string graphs is NP-hard
• Solving systems of polynomial inequalities in subexponential time
• String graphs requiring exponential representations
• The max clique problem in classes of string-graphs
• A special planar satisfiability problem and a consequence of its NP- completeness
• Intersection graphs of segments
• The Intrinsic Spread of a Configuration in R d
• Every planar graph is the intersection graph of segments in the plane
• Recognizing string graphs in NP

This page was built for publication: Segment representations with small resolution