Geodesic
A new algorithm for embedding plane graphs at fixed vertex locations
Marcus Schaefer1
1DePaul University
The electronic journal of combinatorics, Tome 28 (2021) no. 4
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

We show that a plane graph can be embedded with its vertices at pre-assigned (fixed) locations in the plane and at most $2.5n + 1$ bends per edge. This improves and simplifies a classic result by Pach and Wenger. The proof extends to grid embeddings, orthogonal embeddings, and minimum length embeddings.
DOI : 10.37236/10106
Classification : 05C60, 05C10, 05C85, 05C62, 68R10
Mots-clés : graph embedding, planar graph, fixed-vertex location

Marcus Schaefer  1

1 DePaul University 
@article{10_37236_10106,
     author = {Marcus Schaefer},
     title = {A new algorithm for embedding plane graphs at fixed vertex locations},
     journal = {The electronic journal of combinatorics},
     year = {2021},
     volume = {28},
     number = {4},
     doi = {10.37236/10106},
     zbl = {1490.05186},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/10106/}
}
TY  - JOUR
AU  - Marcus Schaefer
TI  - A new algorithm for embedding plane graphs at fixed vertex locations
JO  - The electronic journal of combinatorics
PY  - 2021
VL  - 28
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.37236/10106/
DO  - 10.37236/10106
ID  - 10_37236_10106
ER  - 
%0 Journal Article
%A Marcus Schaefer
%T A new algorithm for embedding plane graphs at fixed vertex locations
%J The electronic journal of combinatorics
%D 2021
%V 28
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/10106/
%R 10.37236/10106
%F 10_37236_10106
Marcus Schaefer. A new algorithm for embedding plane graphs at fixed vertex locations. The electronic journal of combinatorics, Tome 28 (2021) no. 4. doi: 10.37236/10106

Cité par Sources :