Geodesic
Fixed-Location Circular Arc Drawing of Planar Graphs
Journal of Graph Algorithms and Applications, Tome 11 (2007) no. 1, pp. 145-164.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

In this paper we consider the problem of drawing a planar graph using circular arcs as edges, given a one-to-one mapping between the vertices of the graph and a set of points in the plane. If for every edge we have only two possible circular arcs, then a simple reduction to 2SAT yields an O(n2) algorithm to find out if a drawing with no crossings can be realized, where n is the number of vertices in the graph. We present an improved O(n7/4polylog n) time algorithm for this problem. For the special case where the possible circular arcs for each edge are of the same length, we present an even more efficient algorithm that runs in O(n3/2polylog n) time. We also consider two related optimization versions of the problem. First we show that minimizing the number of crossings is NP-hard. Second we show that maximizing the number of edges that can be realized without crossings is also NP-hard. Finally, we show that if we have three or more possible circular arcs per edge, deciding whether a drawing with no crossings can be realized is NP-hard. 
@article{JGAA_2007_11_1_a5,
     author = {Alon Efrat and Cesim Erten and Stephen Kobourov},
     title = {Fixed-Location {Circular} {Arc} {Drawing} of {Planar} {Graphs}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {145--164},
     publisher = {mathdoc},
     volume = {11},
     number = {1},
     year = {2007},
     doi = {10.7155/jgaa.00140},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00140/}
}
TY  - JOUR
AU  - Alon Efrat
AU  - Cesim Erten
AU  - Stephen Kobourov
TI  - Fixed-Location Circular Arc Drawing of Planar Graphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2007
SP  - 145
EP  - 164
VL  - 11
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00140/
DO  - 10.7155/jgaa.00140
LA  - en
ID  - JGAA_2007_11_1_a5
ER  - 
%0 Journal Article
%A Alon Efrat
%A Cesim Erten
%A Stephen Kobourov
%T Fixed-Location Circular Arc Drawing of Planar Graphs
%J Journal of Graph Algorithms and Applications
%D 2007
%P 145-164
%V 11
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00140/
%R 10.7155/jgaa.00140
%G en
%F JGAA_2007_11_1_a5
Alon Efrat; Cesim Erten; Stephen Kobourov. Fixed-Location Circular Arc Drawing of Planar Graphs. Journal of Graph Algorithms and Applications, Tome 11 (2007) no. 1, pp. 145-164. doi : 10.7155/jgaa.00140. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00140/

Cité par Sources :