Geodesic
The Complexity of Simultaneous Geometric Graph Embedding
Journal of Graph Algorithms and Applications, Tome 19 (2015) no. 1, pp. 259-272.

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

Given a collection of planar graphs G1,...,Gk on the same set V of n vertices, the simultaneous geometric embedding (with mapping) problem, or simply k-SGE, is to find a set P of n points in the plane and a bijection φ: V → P such that the induced straight-line drawings of G1,...,Gk under φ are all plane. This problem is polynomial-time equivalent to weak rectilinear realizability of abstract topological graphs, which Kyncl (doi:10.1007/s00454-010-9320-x) proved to be complete for ∃R, the existential theory of the reals. Hence the problem k-SGE is polynomial-time equivalent to several other problems in computational geometry, such as recognizing intersection graphs of line segments or finding the rectilinear crossing number of a graph. We give an elementary reduction from the pseudoline stretchability problem to k-SGE, with the property that both numbers k and n are linear in the number of pseudolines. This implies not only the ∃R-hardness result, but also a 22Ω(n) lower bound on the minimum size of a grid on which any such simultaneous embedding can be drawn. This bound is tight. Hence there exists such collections of graphs that can be simultaneously embedded, but every simultaneous drawing requires an exponential number of bits per coordinates. The best value that can be extracted from Kyncl's proof is only 22Ω(√n).
DOI : 10.7155/jgaa.00356
Keywords: simultaneous geometric embedding, graph drawing, complexity, radial systems 
@article{JGAA_2015_19_1_a10,
     author = {Jean Cardinal and Vincent Kusters},
     title = {The {Complexity} of {Simultaneous} {Geometric} {Graph} {Embedding}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {259--272},
     publisher = {mathdoc},
     volume = {19},
     number = {1},
     year = {2015},
     doi = {10.7155/jgaa.00356},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00356/}
}
TY  - JOUR
AU  - Jean Cardinal
AU  - Vincent Kusters
TI  - The Complexity of Simultaneous Geometric Graph Embedding
JO  - Journal of Graph Algorithms and Applications
PY  - 2015
SP  - 259
EP  - 272
VL  - 19
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00356/
DO  - 10.7155/jgaa.00356
LA  - en
ID  - JGAA_2015_19_1_a10
ER  - 
%0 Journal Article
%A Jean Cardinal
%A Vincent Kusters
%T The Complexity of Simultaneous Geometric Graph Embedding
%J Journal of Graph Algorithms and Applications
%D 2015
%P 259-272
%V 19
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00356/
%R 10.7155/jgaa.00356
%G en
%F JGAA_2015_19_1_a10
Jean Cardinal; Vincent Kusters. The Complexity of Simultaneous Geometric Graph Embedding. Journal of Graph Algorithms and Applications, Tome 19 (2015) no. 1, pp. 259-272. doi : 10.7155/jgaa.00356. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00356/

Cité par Sources :