20:
573:. However, for certain restricted classes of drawings, including drawings of trees in which extending the leaves to infinity produces a convex subdivision of the plane as well as drawings of planar graphs in which each bounded face is a centrally-symmetric polygon, a drawing of optimal angular resolution may be found in
306:
provided an example showing that there exist graphs that do not have a drawing achieving the maximum possible angular resolution; instead, these graphs have a family of drawings whose angular resolutions tend towards some limiting value without reaching it. Specifically, they exhibited an 11-vertex
344:. However, if the cyclic ordering of the edges around each vertex is already determined as part of the input to the problem, then achieving perfect angular resolution with no crossings may sometimes require exponential area.
592:
Although originally defined only for straight-line drawings of graphs, later authors have also investigated the angular resolution of drawings in which the edges are polygonal chains, circular arcs, or spline curves.
336:. Moreover, if the edges may be freely permuted around each vertex, then such a drawing is possible, without crossings, with all edges unit length or higher, and with the entire drawing fitting within a
459:
356:, because vertices on the convex hull of the drawing with degree greater than one cannot have their incident edges equally spaced around them. Nonetheless, every outerplanar graph of maximum degree
293:
506:
142:
523:
is the degree of the graph. Additionally, such a drawing may be forced to use very long edges, longer by an exponential factor than the shortest edges in the drawing.
918:; Kobourov, Stephen G.; Nöllenburg, Martin (2011), "Drawing trees with perfect angular resolution and polynomial area", in Brandes, Ulrik; Cornelsen, Sabine (eds.),
1078:
Garg, Ashim; Tamassia, Roberto (1995), "On the computational complexity of upward and rectilinear planarity testing", in
Tamassia, Roberto; Tollis, Ioannis (eds.),
790:
Data
Visualization 2000: Proceedings of the Joint Eurographics and IEEE TCVG Symposium on Visualization in Amsterdam, the Netherlands, May 29-31, 2000
950:
1128:
995:
Graph
Drawing, 12th International Symposium, GD 2004, New York, NY, USA, September 29-October 2, 2004, Revised Selected Papers
401:
1209:
245:
223:
close to the polygon vertex with the same color. Using this construction, they showed that every graph with maximum degree
1238:
Molloy, Michael; Salavatipour, Mohammad R. (2005), "A bound on the chromatic number of the square of a planar graph",
868:
806:
1061:
865:
Graph
Drawing, 7th International Symposium, GD'99, Štirín Castle, Czech Republic September 15–19, 1999, Proceedings
43:
of a drawing of a graph is the sharpest angle formed by any two edges that meet at a common vertex of the drawing.
398:. More precisely, Wegner conjectured in 1977 that the chromatic number of the square of a planar graph is at most
177:, the graph on the same vertex set in which pairs of vertices are connected by an edge whenever their distance in
1240:
332:
Every tree may be drawn in such a way that the edges are equally spaced around each vertex, a property known as
1178:
597:
1062:
Algorithms, Second Annual
European Symposium, Utrecht, The Netherlands, September 26–28, 1994, Proceedings
464:
112:
1026:
892:
596:
The angular resolution of a graph is closely related to its crossing resolution, the angle formed by
1126:
Halupczok, Immanuel; Schulz, André (2011), "Pinning balloons with perfect angles and optimal area",
1082:, Lecture Notes in Computer Science, vol. 894, Springer Berlin / Heidelberg, pp. 286–297,
1289:
528:
511:
For some planar graphs, the optimal angular resolution of a planar straight-line drawing is
1271:
1230:
1199:
1168:
1118:
1047:
1021:
341:
235:
1207:
Malitz, Seth; Papakostas, Achilleas (1994), "On the angular resolution of planar graphs",
8:
1013:
915:
895:: 11th International Symposium, WADS 2009, Banff, Canada, August 21-23, 2009. Proceedings
860:
997:, Lecture Notes in Computer Science, vol. 3383, Springer-Verlag, pp. 448–453,
922:, Lecture Notes in Computer Science, vol. 6502, Springer-Verlag, pp. 183–194,
788:
1176:
Kramer, Florica; Kramer, Horst (2008), "A survey on the distance-colouring of graphs",
977:
959:
923:
847:
829:
1105:, Lecture Notes in Comput. Sci., vol. 1547, Berlin: Springer, pp. 167–182,
1065:, Lecture Notes in Computer Science, vol. 855, Springer-Verlag, pp. 12–23,
802:
543:
has a planar drawing whose angular resolution is at worst an exponential function of
353:
169:
981:
851:
1257:
1249:
1218:
1187:
1154:
1146:
1106:
1083:
1066:
1056:
1035:
998:
990:
969:
933:
898:
872:
839:
794:
784:
165:
394:, because the square of a planar graph must have chromatic number proportional to
1267:
1226:
1195:
1164:
1114:
1043:
1003:
937:
902:
821:
787:(2000), "Improving angular resolution in visualizations of geographic networks",
574:
210:
24:
948:; Wortman, K. (2011), "Optimal angular resolution for face-symmetric drawings",
843:
798:
508:. However, the drawings resulting from this technique are generally not planar.
1253:
1191:
945:
911:
817:
144:, because this is the best resolution that can be achieved for a vertex on the
1222:
1088:
1283:
1110:
877:
780:
106:
36:
820:(2007), "Trees with convex faces and optimal angles", in Kaufmann, Michael;
1098:
536:
376:
337:
1150:
1059:(1994), "Planar drawings and angular resolution: Algorithms and bounds",
887:
605:
601:
145:
59:
observed that every straight-line drawing of a graph with maximum degree
890:; Liotta, Giuseppe (2009), "Drawing graphs with right angle crossings",
1137:
Kant, G. (1996), "Drawing planar graphs using the canonical ordering",
1070:
973:
897:, Lecture Notes in Computer Science, vol. 5664, pp. 206–217,
532:
1159:
863:; Kobourov, S. G. (1999), "Drawing planar graphs with circular arcs",
834:
1262:
1017:
993:(2005), "Curvilinear graph drawing using the force-directed method",
1039:
555:
It is NP-hard to determine whether a given graph of maximum degree
360:
has an outerplanar drawing with angular resolution proportional to
1011:
964:
928:
683:
586:
384:
315:, but that does not have a drawing of angular resolution exactly
303:
157:
56:
1101:(1998), "Planar polyline drawings with good angular resolution",
94:, and the smallest of these wedges must have an angle of at most
1129:
19:
909:
735:
623:
757:
1024:(1993), "Drawing graphs in the plane with high resolution",
858:
731:
387:
provides a drawing with angular resolution proportional to
160:
showed, the largest possible angular resolution of a graph
1012:
Formann, M.; Hagerup, T.; Haralambides, J.; Kaufmann, M.;
828:, LNCS, vol. 4372, Springer-Verlag, pp. 77–88,
461:, and it is known that the chromatic number is at most
454:{\displaystyle \max \left(d+5,{\frac {3d}{2}}+1\right)}
779:
747:
547:, independent of the number of vertices in the graph.
352:
Perfect angular resolution is not always possible for
227:
has a drawing with angular resolution proportional to
871:, vol. 1731, Springer-Verlag, pp. 117–126,
467:
404:
288:{\displaystyle O\left({\frac {\log d}{d^{2}}}\right)}
248:
238:
to prove the existence of graphs with maximum degree
115:
209:, by assigning distinct colors to the vertices of a
1237:
659:
500:
453:
287:
136:
885:
763:
1281:
1206:
639:
524:
405:
298:
1125:
1096:
944:
815:
719:
703:
699:
627:
307:graph that has drawings of angular resolution
988:
751:
234:. This bound is close to tight: they used the
151:
1175:
1077:
1054:
951:Journal of Graph Algorithms and Applications
687:
671:
655:
643:
322:
109:, it must have angular resolution less than
51:
826:Proc. 14th Int. Symp. Graph Drawing (GD'06)
550:
242:whose drawings all have angular resolution
604:seeks to ensure that these angles are all
600:in a drawing of the graph. In particular,
1261:
1158:
1087:
1002:
963:
927:
876:
833:
585:Angular resolution was first defined by
18:
16:Sharpest angle between edges at a vertex
608:, the largest crossing angle possible.
1282:
748:Brandes, Shubina & Tamassia (2000)
559:has a drawing with angular resolution
197:may be drawn with angular resolution
347:
1210:SIAM Journal on Discrete Mathematics
1136:
715:
501:{\displaystyle {\frac {5d}{3}}+O(1)}
920:Proc. 18th Int. Symp. Graph Drawing
383:, the square-coloring technique of
137:{\displaystyle {\frac {\pi }{d-1}}}
13:
1103:Graph drawing (Montréal, QC, 1998)
14:
1301:
869:Lecture Notes in Computer Science
764:Didimo, Eades & Liotta (2009)
566:, even in the special case that
660:Molloy & Salavatipour (2005)
370:
63:has angular resolution at most
1241:Journal of Combinatorial Theory
101:. More strongly, if a graph is
893:Algorithms and Data Structures
741:
725:
709:
693:
677:
665:
649:
640:Malitz & Papakostas (1994)
633:
617:
525:Malitz & Papakostas (1994)
495:
489:
1:
859:Cheng, C. C.; Duncan, C. A.;
772:
720:Gutwenger & Mutzel (1998)
704:Eppstein & Wortman (2011)
700:Carlson & Eppstein (2007)
628:Halupczok & Schulz (2011)
299:Existence of optimal drawings
78:, then the edges incident to
46:
1004:10.1007/978-3-540-31843-9_46
938:10.1007/978-3-642-18469-7_17
903:10.1007/978-3-642-03367-4_19
752:Finkel & Tamassia (2005)
7:
844:10.1007/978-3-540-70904-6_9
799:10.1007/978-3-7091-6783-0_3
219:and placing each vertex of
82:partition the space around
10:
1306:
1254:10.1016/j.jctb.2004.12.005
1192:10.1016/j.disc.2006.11.059
688:Garg & Tamassia (1995)
672:Garg & Tamassia (1994)
656:Kramer & Kramer (2008)
644:Garg & Tamassia (1994)
580:
334:perfect angular resolution
164:is closely related to the
152:Relation to graph coloring
1223:10.1137/S0895480193242931
1089:10.1007/3-540-58950-3_384
1027:SIAM Journal on Computing
323:Special classes of graphs
52:Relation to vertex degree
1111:10.1007/3-540-37623-2_13
878:10.1007/3-540-46648-7_12
611:
551:Computational complexity
327:
90:wedges with total angle
27:has angular resolution
910:Duncan, Christian A.;
529:circle packing theorem
502:
455:
289:
138:
74:is a vertex of degree
32:
1151:10.1007/s004539900035
684:Formann et al. (1993)
587:Formann et al. (1993)
503:
456:
385:Formann et al. (1993)
304:Formann et al. (1993)
290:
158:Formann et al. (1993)
139:
57:Formann et al. (1993)
22:
1179:Discrete Mathematics
1097:Gutwenger, Carsten;
916:Goodrich, Michael T.
736:Duncan et al. (2011)
624:Duncan et al. (2011)
539:with maximum degree
465:
402:
379:with maximum degree
246:
236:probabilistic method
187:can be colored with
113:
783:; Shubina, Galina;
732:Cheng et al. (1999)
535:to show that every
181:is at most two. If
1071:10.1007/BFb0049393
989:Finkel, Benjamin;
974:10.7155/jgaa.00238
498:
451:
354:outerplanar graphs
348:Outerplanar graphs
285:
134:
41:angular resolution
33:
23:This drawing of a
1057:Tamassia, Roberto
991:Tamassia, Roberto
816:Carlson, Josiah;
785:Tamassia, Roberto
481:
438:
279:
132:
1297:
1274:
1265:
1233:
1202:
1186:(2–3): 422–426,
1171:
1162:
1132:
1121:
1092:
1091:
1073:
1050:
1034:(5): 1035–1052,
1016:; Symvonis, A.;
1007:
1006:
984:
967:
940:
931:
905:
886:Didimo, Walter;
881:
880:
854:
837:
822:Wagner, Dorothea
811:
767:
761:
755:
745:
739:
729:
723:
713:
707:
697:
691:
681:
675:
669:
663:
653:
647:
637:
631:
621:
572:
565:
558:
546:
542:
522:
518:
507:
505:
504:
499:
482:
477:
469:
460:
458:
457:
452:
450:
446:
439:
434:
426:
397:
393:
382:
366:
359:
318:
314:
310:
294:
292:
291:
286:
284:
280:
278:
277:
268:
257:
241:
233:
226:
222:
216:
208:
204:
192:
186:
180:
176:
166:chromatic number
163:
148:of the drawing.
143:
141:
140:
135:
133:
131:
117:
104:
100:
93:
89:
85:
81:
77:
73:
69:
62:
30:
1305:
1304:
1300:
1299:
1298:
1296:
1295:
1294:
1280:
1279:
1278:
1040:10.1137/0222063
1014:Leighton, F. T.
912:Eppstein, David
861:Goodrich, M. T.
818:Eppstein, David
809:
775:
770:
762:
758:
746:
742:
730:
726:
714:
710:
698:
694:
682:
678:
670:
666:
654:
650:
638:
634:
622:
618:
614:
583:
575:polynomial time
567:
560:
556:
553:
544:
540:
520:
512:
470:
468:
466:
463:
462:
427:
425:
412:
408:
403:
400:
399:
395:
388:
380:
373:
361:
357:
350:
330:
325:
316:
312:
308:
301:
273:
269:
258:
256:
252:
247:
244:
243:
239:
228:
224:
220:
212:
206:
198:
188:
182:
178:
172:
161:
154:
121:
116:
114:
111:
110:
102:
95:
91:
87:
83:
79:
75:
71:
64:
60:
54:
49:
28:
25:hypercube graph
17:
12:
11:
5:
1303:
1293:
1292:
1277:
1276:
1248:(2): 189–213,
1235:
1217:(2): 172–183,
1204:
1173:
1134:
1123:
1094:
1075:
1052:
1009:
986:
958:(4): 551–564,
942:
907:
883:
856:
813:
807:
781:Brandes, Ulrik
776:
774:
771:
769:
768:
756:
740:
724:
708:
692:
676:
664:
648:
632:
615:
613:
610:
582:
579:
552:
549:
497:
494:
491:
488:
485:
480:
476:
473:
449:
445:
442:
437:
433:
430:
424:
421:
418:
415:
411:
407:
372:
369:
349:
346:
340:of polynomial
329:
326:
324:
321:
300:
297:
283:
276:
272:
267:
264:
261:
255:
251:
203: − ε
153:
150:
130:
127:
124:
120:
53:
50:
48:
45:
15:
9:
6:
4:
3:
2:
1302:
1291:
1290:Graph drawing
1288:
1287:
1285:
1273:
1269:
1264:
1259:
1255:
1251:
1247:
1243:
1242:
1236:
1232:
1228:
1224:
1220:
1216:
1212:
1211:
1205:
1201:
1197:
1193:
1189:
1185:
1181:
1180:
1174:
1170:
1166:
1161:
1156:
1152:
1148:
1144:
1140:
1135:
1131:
1130:
1124:
1120:
1116:
1112:
1108:
1104:
1100:
1099:Mutzel, Petra
1095:
1090:
1085:
1081:
1080:Graph Drawing
1076:
1072:
1068:
1064:
1063:
1058:
1055:Garg, Ashim;
1053:
1049:
1045:
1041:
1037:
1033:
1029:
1028:
1023:
1022:Woeginger, G.
1019:
1015:
1010:
1005:
1000:
996:
992:
987:
983:
979:
975:
971:
966:
961:
957:
953:
952:
947:
943:
939:
935:
930:
925:
921:
917:
913:
908:
904:
900:
896:
894:
889:
884:
879:
874:
870:
866:
862:
857:
853:
849:
845:
841:
836:
835:cs.CG/0607113
831:
827:
823:
819:
814:
810:
808:9783211835159
804:
800:
796:
792:
791:
786:
782:
778:
777:
765:
760:
753:
749:
744:
737:
733:
728:
721:
717:
712:
705:
701:
696:
689:
685:
680:
673:
668:
661:
657:
652:
645:
641:
636:
629:
625:
620:
616:
609:
607:
603:
599:
594:
590:
588:
578:
576:
570:
564:
548:
538:
534:
530:
526:
516:
509:
492:
486:
483:
478:
474:
471:
447:
443:
440:
435:
431:
428:
422:
419:
416:
413:
409:
392:
386:
378:
377:planar graphs
371:Planar graphs
368:
365:
355:
345:
343:
339:
335:
320:
305:
296:
281:
274:
270:
265:
262:
259:
253:
249:
237:
232:
218:
215:
202:
196:
193:colors, then
191:
185:
175:
171:
167:
159:
149:
147:
128:
125:
122:
118:
108:
99:
68:
58:
44:
42:
38:
37:graph drawing
26:
21:
1245:
1244:, Series B,
1239:
1214:
1208:
1183:
1177:
1142:
1139:Algorithmica
1138:
1127:
1102:
1079:
1060:
1031:
1025:
994:
955:
949:
946:Eppstein, D.
919:
891:
888:Eades, Peter
864:
825:
789:
759:
743:
727:
711:
695:
679:
667:
651:
635:
619:
606:right angles
595:
591:
584:
568:
562:
554:
537:planar graph
514:
510:
390:
374:
363:
351:
338:bounding box
333:
331:
302:
230:
213:
200:
194:
189:
183:
173:
155:
97:
66:
55:
40:
34:
1145:(1): 4–32,
716:Kant (1996)
602:RAC drawing
205:, for any
146:convex hull
1160:1874/16676
773:References
533:ring lemma
47:Properties
1263:1807/9473
1018:Welzl, E.
965:0907.5474
929:1009.0581
598:crossings
527:used the
311:for any
263:
126:−
119:π
1284:Category
982:10356432
852:12598338
824:(eds.),
519:, where
313:ε > 0
211:regular
207:ε > 0
1272:2145512
1231:1271989
1200:2378044
1169:1394492
1119:1717450
1048:1237161
581:History
309:π/3 − ε
168:of the
107:regular
1270:
1229:
1198:
1167:
1117:
1046:
980:
850:
805:
170:square
39:, the
978:S2CID
960:arXiv
924:arXiv
848:S2CID
830:arXiv
612:Notes
328:Trees
86:into
70:: if
803:ISBN
531:and
513:O(1/
375:For
342:area
217:-gon
1258:hdl
1250:doi
1219:doi
1188:doi
1184:308
1155:hdl
1147:doi
1107:doi
1084:doi
1067:doi
1036:doi
999:doi
970:doi
934:doi
899:doi
873:doi
840:doi
795:doi
571:= 4
561:2π/
406:max
317:π/3
260:log
156:As
96:2π/
65:2π/
35:In
29:π/4
1286::
1268:MR
1266:,
1256:,
1246:94
1227:MR
1225:,
1213:,
1196:MR
1194:,
1182:,
1165:MR
1163:,
1153:,
1143:16
1141:,
1115:MR
1113:,
1044:MR
1042:,
1032:22
1030:,
1020:;
976:,
968:,
956:15
954:,
932:,
914:;
867:,
846:,
838:,
801:,
793:,
750:;
734:;
718:;
702:;
686:;
658:;
642:;
626:;
589:.
577:.
389:1/
367:.
362:1/
319:.
295:.
229:1/
199:π/
92:2π
1275:.
1260::
1252::
1234:.
1221::
1215:7
1203:.
1190::
1172:.
1157::
1149::
1133:.
1122:.
1109::
1093:.
1086::
1074:.
1069::
1051:.
1038::
1008:.
1001::
985:.
972::
962::
941:.
936::
926::
906:.
901::
882:.
875::
855:.
842::
832::
812:.
797::
766:.
754:.
738:.
722:.
706:.
690:.
674:.
662:.
646:.
630:.
569:d
563:d
557:d
545:d
541:d
521:d
517:)
515:d
496:)
493:1
490:(
487:O
484:+
479:3
475:d
472:5
448:)
444:1
441:+
436:2
432:d
429:3
423:,
420:5
417:+
414:d
410:(
396:d
391:d
381:d
364:d
358:d
282:)
275:2
271:d
266:d
254:(
250:O
240:d
231:d
225:d
221:G
214:χ
201:χ
195:G
190:χ
184:G
179:G
174:G
162:G
129:1
123:d
105:-
103:d
98:d
88:d
84:v
80:v
76:d
72:v
67:d
61:d
31:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
