Curve-constrained drawings of planar graphs (Q706719)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 2132540
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Curve-constrained drawings of planar graphs |
scientific article; zbMATH DE number 2132540 |
Statements
Curve-constrained drawings of planar graphs (English)
0 references
9 February 2005
0 references
The authors study 2D-drawings of graphs where the vertices are constrained to be on a given curve and the edges have at most one bend. Introducing the concept of a curve embedding of a planar graph, they prove that every planar graph admits a curve embedding and presents a linear-time algorithm to compute one [cf. \textit{F. Bernhart} and \textit{P. C. Kainen}, J. Comb. Theory, Ser. B 27, 320--331 (1979; Zbl 0427.05028)]. Interplay between curve embeddings and upward drawings is also studied. Curve embeddings are also used to simplify and extend the algorithm of \textit{M. Kaufmann} and \textit{R. Wiese} [J. Graph Algorithms Appl. 6, 115--129 (2002; Zbl 0999.68164)] for point set embeddability.
0 references
curve embeddings
0 references
point-set embedding
0 references
graph drawing
0 references
0 references
0 references
0.9388483762741088
0 references
0.8740509748458862
0 references
0.8722216486930847
0 references
0.8272404670715332
0 references
0.7972456812858582
0 references
