TY - GEN
T1 - Polar coordinate drawing of planar graphs with good angular resolution
AU - Duncan, Christian A.
AU - Kobourov, Stephen G.
PY - 2002
Y1 - 2002
N2 - We present a novel way to draw planar graphs with good angular resolution. We introduce the polar coordinate representation and describe a family of algorithms which use polar representation. The main advantage of using a polar representation is that it allows us to exert independent control over grid size and bend positions. Polar coordinates allow us to specify different vertex resolution, bend-point resolution and edge separation. We first describe a standard (Cartesian) representation algorithm (CRA) which we then modify to obtain a polar representation algorithm (PRA). In both algorithms we are concerned with the following drawing criteria: angular resolution, bends per edge, vertex resolution, bend-point resolution, edge separation, and drawing area. The CRA algorithm achieves 1 bend per edge, unit vertex and bend resolution, √2/2 edge separation, 5n × 5n/2 drawing area and 1/2d(v) angular resolution, where d(v) is the degree of vertex v. The PRA algorithm has an improved angular resolution of φ/4d(v) 1 bend per edge, and unit vertex resolution. For the PRA algorithm, the bend-point resolution and edge separation are parameters that can be modified to achieve different types of drawings and drawing areas. In particular, for the same parameters as the CRA algorithm (unit bend-point resolution and √2/2 edge separation), the PRA algorithm creates a drawing of size 9n × 9n/2.
AB - We present a novel way to draw planar graphs with good angular resolution. We introduce the polar coordinate representation and describe a family of algorithms which use polar representation. The main advantage of using a polar representation is that it allows us to exert independent control over grid size and bend positions. Polar coordinates allow us to specify different vertex resolution, bend-point resolution and edge separation. We first describe a standard (Cartesian) representation algorithm (CRA) which we then modify to obtain a polar representation algorithm (PRA). In both algorithms we are concerned with the following drawing criteria: angular resolution, bends per edge, vertex resolution, bend-point resolution, edge separation, and drawing area. The CRA algorithm achieves 1 bend per edge, unit vertex and bend resolution, √2/2 edge separation, 5n × 5n/2 drawing area and 1/2d(v) angular resolution, where d(v) is the degree of vertex v. The PRA algorithm has an improved angular resolution of φ/4d(v) 1 bend per edge, and unit vertex resolution. For the PRA algorithm, the bend-point resolution and edge separation are parameters that can be modified to achieve different types of drawings and drawing areas. In particular, for the same parameters as the CRA algorithm (unit bend-point resolution and √2/2 edge separation), the PRA algorithm creates a drawing of size 9n × 9n/2.
UR - http://www.scopus.com/inward/record.url?scp=23044533409&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=23044533409&partnerID=8YFLogxK
U2 - 10.1007/3-540-45848-4_32
DO - 10.1007/3-540-45848-4_32
M3 - Conference contribution
AN - SCOPUS:23044533409
SN - 3540433090
SN - 9783540433095
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 407
EP - 421
BT - Graph Drawing - 9th International Symposium, GD 2001, Revised Papers
A2 - Mutzel, Petra
A2 - Junger, Michael
A2 - Leipert, Sebastian
PB - Springer-Verlag
T2 - 9th International Symposium on Graph Drawing, GD 2001
Y2 - 23 September 2001 through 26 September 2001
ER -