Simultaneous embeddings with vertices mapping to pre-specified points

DOI10.1007/978-3-642-32241-9_26MaRDI QIDQ2914335zbMATH OpenOpenAlexFDO

Authors Taylor Gordon

Publication date 25 September 2012

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

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

zbMATH Keywords

uniformly random planar graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: We discuss the problem of embedding graphs in the plane with restrictions on the vertex mapping. In particular, we introduce a technique for drawing planar graphs with a fixed vertex mapping that bounds the number of times edges bend. An immediate consequence of this technique is that any planar graph can be drawn with a fixed vertex mapping so that edges map to piecewise linear curves with at most $3n+O(1)$ bends each. By considering uniformly random planar graphs, we show that $2n+O(1)$ bends per edge is sufficient on average. To further utilize our technique, we consider simultaneous embeddings of $k$ uniformly random planar graphs with vertices mapping to a fixed, common point set. We explain how to achieve such a drawing so that edges map to piecewise linear curves with $O(n^{1-1/k})$ bends each, which holds with overwhelming probability. This result improves upon the previously best known result of O(n) bends per edge for the case where $kgeq2$. Moreover, we give a lower bound on the number of bends that matches our upper bound, proving our results are optimal.

Recommendations

• Simultaneous Embedding with Two Bends per Edge in Polynomial Area
• Embedding planar graphs at fixed vertex locations
• Simultaneous Embedding of Planar Graphs with Few Bends
• Simultaneous graph embedding with bends and circular arcs
• On simultaneous planar graph embeddings

Cited in

(3)

• A new algorithm for embedding plane graphs at fixed vertex locations
• Relating graph thickness to planar layers and bend complexity
• Simultaneous Embedding

This page was built for publication: Simultaneous embeddings with vertices mapping to pre-specified points

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