Fractional Lengths and Crossing Numbers

Sýkora, Ondrej and Székely, László A. and Vrt'o, Imrich (2002) Fractional Lengths and Crossing Numbers. In: Graph Drawing 10th International Symposium, GD 2002, August 26-28, 2002, Irvine, CA, USA , pp. 186-192 (Official URL: http://dx.doi.org/10.1007/3-540-36151-0_18).

Full text not available from this repository.

Abstract

Adamec and Nesetril [1] proposed a new the so called fractional length criterion for measuring the aesthetics of (artistic) drawings. They proposed to apply the criterion to the aesthetic drawing of graphs. In the graph drawing community, it is widely believed and even experimentally confirmed that the number of crossings is one of the most important aesthetic measures for nice drawings of graphs [6]. The aim of this note is to demonstrate on two standard graph drawing models that in provably good drawings, with respect to the crossing number measure, the fractional length criterion is closely related to the crossing number criterion.

Item Type:Conference Paper
Additional Information:10.1007/3-540-36151-0_18
Classifications:G Algorithms and Complexity > G.420 Crossings
D Aesthetics > D.001 General
ID Code:253

Repository Staff Only: item control page

References

Adamec, J., Nesetril,J.: Towards an Aesthetic Invariant for Graph Drawing. In: 9th Intl. Symp. on Graph Drawing. LNCS 2265. Springer. Berlin (2001) 287-296

Bhatt, S., Leighton, F.T.: A Framework for Solving VLSI Graph Layout Problems. J. Computer and System Science 28 (1984) 300-334

DiBattista, G., Eades, P., Tollis, I., Tamassia, R.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall (1999)

Leighton, F.T.: New Lower Bound Techniques for VLSI. Mathematical Systems Theory 17 (1984) 47-70

Leiserson, C.E.: Area Efficient Graph Layouts (for VLSI). In: 21st Annual Symposium on Foundations of Computer Science. IEEE Press (1980) 270-281

Purchase, H.: Which aesthetic has the greatest effct on Human Understanding? In: 5th Intl. Symp. on Graph Drawing. LNCS 1353. Springer. Berlin (1997) 248-261

Shahrokhi, F., Sýkora, O., Székely, L.A., Vrt'o, I.: On Bipartite Drawings and the Linear Arrangement Problem. SIAM J. Computing 30 (2000), 1773-1789.

Steinhaus, H.: Length, Shape and Area. Colloquium Math. III (1954) 1-13

Thompson, C.D.: Area-Time Complexity for VLSI. In: 11th Annual ACM Symposium on Theory Computing. ACM Press (1979) 81-89

Valiant, L.G.: Universality Considerations in VLSI Circuits. IEEE Transactions on Computers 30 (1981) 135-140