Geodesic
Planar Graphs with Topological Constraints
Journal of Graph Algorithms and Applications, Selected Papers from the 1999 Symposium on Graph Drawing , Tome 6 (2002) no. 1, pp. 27-66.

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

We address in this paper the problem of constructing embeddings of planar graphs satisfying declarative, user-defined topological constraints. The constraints consist each of a cycle of the given graph and a set of its edges to be embedded inside this cycle and a set of its edges to be embedded outside this cycle. Their practical importance in graph visualization applications is due to the capability of supporting the semantics of graphs. Additionally, embedding algorithms for planar graphs with topological constraints can be combined with planar graph drawing algorithms that transform a given embedding into a topology preserving drawing according to particular drawing conventions and aesthetic criteria. We obtain the following main results on the planarity problem with topological constraints. Since it turns out to be NP-complete, we develop a polynomial time algorithm for reducing the problem for arbitrary planar graphs to a planarity problem with constraints for biconnected graphs. This allows focussing on biconnected graphs when searching for heuristics or polynomial time subproblems. We then define a particular subproblem by restricting the maximum number of vertices that any two distinct cycles involved in the constraints can have in common. Whereas the problem remains NP-complete if this number exceeds 1, it can otherwise be solved in polynomial time. The embedding algorithm we develop for this purpose is based on the reduction method. 
@article{JGAA_2002_6_1_a2,
     author = {Christoph Dornheim},
     title = {Planar {Graphs} with {Topological} {Constraints}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {27--66},
     publisher = {mathdoc},
     volume = {6},
     number = {1},
     year = {2002},
     doi = {10.7155/jgaa.00044},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00044/}
}
TY  - JOUR
AU  - Christoph Dornheim
TI  - Planar Graphs with Topological Constraints
JO  - Journal of Graph Algorithms and Applications
PY  - 2002
SP  - 27
EP  - 66
VL  - 6
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00044/
DO  - 10.7155/jgaa.00044
LA  - en
ID  - JGAA_2002_6_1_a2
ER  - 
%0 Journal Article
%A Christoph Dornheim
%T Planar Graphs with Topological Constraints
%J Journal of Graph Algorithms and Applications
%D 2002
%P 27-66
%V 6
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00044/
%R 10.7155/jgaa.00044
%G en
%F JGAA_2002_6_1_a2
Christoph Dornheim. Planar Graphs with Topological Constraints. Journal of Graph Algorithms and Applications, 
							Selected Papers from the 1999 Symposium on Graph Drawing
					, Tome 6 (2002) no. 1, pp. 27-66. doi : 10.7155/jgaa.00044. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00044/

Cité par Sources :