Establishing order in planar subdivisions

DOI10.1007/BF02187912zbMath0663.68053OpenAlexW4241317956MaRDI QIDQ1115185

David G. Kirkpatrick

Publication date: 1988

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/131050

zbMATH Keywords

planar graphcomplexity analysisplanar subdivisionnormal digraphsvertex eliminationendpoint embeddingface contractionplanar realizability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Directed graphs (digraphs), tournaments (05C20)

Related Items

Determining bar-representability for ordered weighted graphs ⋮ On the recognition of fan-planar and maximal outer-fan-planar graphs ⋮ Checking the convexity of polytopes and the planarity of subdivisions (extended abstract) ⋮ Checking the convexity of polytopes and the planarity of subdivisions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding the intersection of two convex polyhedra
• On the complexity of computations under varying sets of primitives
• Lower Bounds for Sorting with Realistic Instruction Sets
• Optimal Point Location in a Monotone Subdivision
• Optimal Search in Planar Subdivisions
• Efficient Planarity Testing
• Location of a Point in a Planar Subdivision and Its Applications