Planar subgraphs without low-degree nodes

DOI10.1007/978-3-642-22300-6_49MaRDI QIDQ5199275zbMATH OpenOpenAlexFDO

Authors Oscar Morales-Ponce, Jukka Suomela, Evangelos Kranakis

Publication date 12 August 2011

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-22300-6_49

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On Spanners of Geometric Graphs
• One strike against the min-max degree triangulation problem
• Computing geometric minimum-dilation graphs is NP-hard
• Unit disk graphs
• Planar embeddability of the vertices of a graph using a fixed point set is NP-hard

Cited in

(2)

• Planar graphs without normally adjacent short cycles
• Plane Triangulations Without a Spanning Halin Subgraph: Counterexamples to the Lovász--Plummer Conjecture on Halin Graphs

This page was built for publication: Planar subgraphs without low-degree nodes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5199275)