EDGE CROSSINGS IN LAYERED DRAWINGS OF GRAPHS

Authors
EADES P
Citation
P. Eades, EDGE CROSSINGS IN LAYERED DRAWINGS OF GRAPHS, Zeitschrift fur angewandte Mathematik und Mechanik, 76, 1996, pp. 47-50
Citations number
13
Categorie Soggetti
Mathematics,"Mathematical Method, Physical Science",Mechanics,Mathematics
Journal title
Zeitschrift fur angewandte Mathematik und Mechanik → ACNP
ISSN journal
00442267
Volume
76
Year of publication
1996
Supplement
3
Pages
47 - 50
Database
ISI
SICI code
0044-2267(1996)76:<47:ECILDO>2.0.ZU;2-U
Abstract
The most common commercial technique for drawing directed graphs invol ves partitioning the vertex set V into ''layers'' L(1), L(2),...,L(k). Vertices in L(i) are arranged on the horizontal line y = i. A signifi cant problem for such drawings is to choose an arrangement within each layer so that crossings are avoided. In this talk we discuss the comp utational complexity of choosing such an arrangement.