Untangling planar graphs from a specified vertex position-Hard cases
From MaRDI portal
Publication:534342
DOI10.1016/j.dam.2011.01.011zbMath1219.05046OpenAlexW2012957023MaRDI QIDQ534342
Oleg Pikhurko, Mathias Schacht, Mihyun Kang, Oleg Verbitsky, O. V. Ravskyj
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
Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items (10)
Untangling polygons and graphs ⋮ Upper Bound Constructions for Untangling Planar Geometric Graphs ⋮ Dual circumference and collinear sets ⋮ Untangling circular drawings: algorithms and complexity ⋮ Drawing Planar Graphs with Many Collinear Vertices ⋮ Every collinear set in a planar graph is free ⋮ Unnamed Item ⋮ On Collinear Sets in Straight-Line Drawings ⋮ A polynomial bound for untangling geometric planar graphs ⋮ Untangling a planar graph
Cites Work
- Unnamed Item
- Unnamed Item
- Untangling polygons and graphs
- Descending subsequences of random permutations
- Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences
- On the obfuscation complexity of planar graphs
- A polynomial bound for untangling geometric planar graphs
- Untangling a planar graph
- On the length of the longest monotone subsequence in a random permutation
- The height of a random partial order: Concentration of measure
- Untangling a polygon
- Concentration of measure and isoperimetric inequalities in product spaces
- 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
- Untangling a Planar Graph
- Moving Vertices to Make Drawings Plane
This page was built for publication: Untangling planar graphs from a specified vertex position-Hard cases
