Untangling planar graphs from a specified vertex position-Hard cases

DOI10.1016/J.DAM.2011.01.011MaRDI QIDQ534342zbMATH OpenOpenAlexFDO

Authors Mihyun Kang, Oleg Pikhurko, M. Schacht, Oleg Verbitsky, Oleksandr Ravs'kyj

Publication date 17 May 2011

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2011.01.011

zbMATH Keywords

combinatorial geometryplanar graphsgraph drawinguntangling problem

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)

Recommendations

• Untangling a planar graph
• Untangling a Planar Graph
• Upper bound constructions for untangling planar geometric graphs
• Upper Bound Constructions for Untangling Planar Geometric Graphs
• A polynomial bound for untangling geometric planar graphs
• A Polynomial Bound for Untangling Geometric Planar Graphs
• Planarizing graphs and their drawings by vertex splitting
• Publication:5753968
• scientific article; zbMATH DE number 437535
• The Vertex-Disjoint Menger Problem in Planar Graphs

Cites work

• scientific article; zbMATH DE number 2123122 (Why is no real title available?)
• scientific article; zbMATH DE number 1424289 (Why is no real title available?)
• A polynomial bound for untangling geometric planar graphs
• Concentration of measure and isoperimetric inequalities in product spaces
• Descending subsequences of random permutations
• Moving Vertices to Make Drawings Plane
• On collinear sets in straight-line drawings
• On the Number of Crossing‐Free Matchings, Cycles, and Partitions
• On the distribution of the length of the longest increasing subsequence of random permutations
• On the length of the longest monotone subsequence in a random permutation
• On the obfuscation complexity of planar graphs
• Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences
• The height of a random partial order: Concentration of measure
• Untangling a Planar Graph
• Untangling a planar graph
• Untangling a polygon
• Untangling polygons and graphs

Cited in

(9)

• Drawing planar graphs with many collinear vertices
• Untangling polygons and graphs
• A polynomial bound for untangling geometric planar graphs
• On collinear sets in straight-line drawings
• Untangling a planar graph
• Upper Bound Constructions for Untangling Planar Geometric Graphs
• Dual circumference and collinear sets
• Dual circumference and collinear sets
• Untangling circular drawings: algorithms and complexity

This page was built for publication: Untangling planar graphs from a specified vertex position-Hard cases

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