Leftist Canonical Ordering

Badent, Melanie and Baur, Michael and Brandes, Ulrik and Cornelsen, Sabine (2010) Leftist Canonical Ordering. In: Graph Drawing 17th International Symposium, GD 2009, September 22-25, 2009, Chicago, IL, USA , pp. 159-170 (Official URL: http://dx.doi.org/10.1007/978-3-642-11805-0_16).

Full text not available from this repository.

Abstract

Canonical ordering is an important tool in planar graph drawing and other applications. Although a linear-time algorithm to determine canonical orderings has been known for a while, it is rather complicated to understand and implement, and the output is not uniquely determined. We present a new approach that is simpler and more intuitive, and that computes a newly defined leftist canonical ordering of a triconnected graph which is a uniquely determined leftmost canonical ordering.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-11805-0_16
Classifications:G Algorithms and Complexity > G.280 Canonical Ordering
ID Code:1065

Repository Staff Only: item control page

References

Barbay, J., Aleardi, L.C., He, M., Munro, I.: Succinct Representation of Labeled Graphs. In: Tokuyama, T. (ed.) ISAAC 2007. LNCS, vol. 4835, pp. 316–328. Springer, Heidelberg (2007)

Barequet, G., Goodrich, M.T., Riley, C.: Drawing Planar Graphs with Large Vertices and Thick Edges. J. of Graph Algorithms and Applications 8(1), 3–20 (2004)

Biedl, T.C.: Drawing Planar Partitions I: LL-Drawings and LH-Drawings. In: Proc. 14th Symp. on Computational Geometry, pp. 287–296. ACM Press, New York (1998)

Biedl, T.C., Kaufmann, M.: Area-Efficient Static and Incremental Graph Drawings. In: Burkard, R.E., Woeginger, G.J. (eds.) ESA 1997. LNCS, vol. 1284, pp. 37–52. Springer, Heidelberg (1997)

Bose, P., Gudmundsson, J., Smid, M.: Constructing Plane Spanners of Bounded Degree and Low Weight. Algorithmica 42(3-4), 249–264 (2005)

Brehm, E.: 3-Orientations and Schnyder 3-Tree-Decompositions. Master’s thesis, FU Berlin (2000)

Chiang, Y.-T., Lin, C.-C., Lu, H.-I.: Orderly Spanning Trees with Applications to Graph Encoding and Graph Drawing. In: Proc. 12th ACM–SIAM Symp. on Discrete Algorithms (SODA 2001), pp. 506–515 (2001)

Chrobak, M., Kant, G.: Convex Grid Drawings of 3-Connected Planar Graphs. Int. J. of Computational Geometry and Applications 7(3), 211–223 (1997)

Chrobak, M., Nakano, S.-I.: Minimum-Width Grid Drawings of Plane Graphs. Computational Geometry 11(1), 29–54 (1998)

Chrobak, M., Payne, T.H.: A Linear-Time Algorithm for Drawing a Planar Graph on a Grid. Information Processing Letters 54(4), 241–246 (1995)

Chuang, R.C.-N., Garg, A., He, X., Kao, M.-Y., Lu, H.-I.: Compact Encodings of Planar Graphs via Canonical Orderings and Multiple Parentheses. In: Larsen, K.G., Skyum, S., Winskel, G. (eds.) ICALP 1998. LNCS, vol. 1443, pp. 118–129. Springer, Heidelberg (1998)

de Fraysseix, H., Mendez, P.O.: Regular Orientations, Arboricity, and Augmentation. In: Tamassia, R., Tollis, I.G. (eds.) GD 1994. LNCS, vol. 894, pp. 111–118. Springer, Heidelberg (1995)

de Fraysseix, H., Pach, J., Pollack, R.: Small Sets Supporting F´ry Embeddings of a Planar Graphs. In: Proc. 20th ACM Symp. on the Theory of Computing (STOC 1988), pp. 426–433. ACM Press, New York (1988)

de Fraysseix, H., Pach, J., Pollack, R.: How to Draw a Planar Graph on a Grid. Combinatorica 10(1), 41–51 (1990)

Di Battista, G., Tamassia, R., Vismara, L.: Output-Sensitive Reporting of Disjoint Paths. Algorithmica 23(4), 302–340 (1999) 16. Di Giacomo, E., Didimo, W., Liotta, G.: Radial Drawings of Graphs: Geometric Constraints and Trade-offs. J. of Discrete Algorithms 6(1), 109–124 (2008)

Di Giacomo, E., Didimo, W., Liotta, G., Wismath, S.K.: Curve-Constrained Drawings of Planar Graphs. Computational Geometry 30(2), 1–23 (2005)

Dujmović, V., Suderman, M., Wood, D.R.: Really Straight Graph Drawings. In: GD 2004 [21], pp. 122–132

Erten, C., Kobourov, S.G.: Simultaneous Embedding of Planar Graphs with Few Bends. In: GD 2004 [21], pp. 195–205

Fößmeier, U., Kant, G., Kaufmann, M.: 2-Visibility Drawings of Planar Graphs. In: North, S.C. (ed.) GD 1996. LNCS, vol. 1190, pp. 155–168. Springer, Heidelberg (1997)

Pach, J. (ed.): GD 2004. LNCS, vol. 3383. Springer, Heidelberg (2005) 22. Goodrich, M.T., Wagner, C.G.: A Framework for Drawing Planar Graphs with Curves and Polylines. J. of Algorithms 37(2), 399–421 (2000)

Gutwenger, C., Mutzel, P.: Planar Polyline Drawings with Good Angular Resolution. In: Whitesides, S.H. (ed.) GD 1998. LNCS, vol. 1547, pp. 167–182. Springer, Heidelberg (1999)

Harel, D., Sardas, M.: An Algorithm for Straight-Line Drawing of Planar Graphs. Algorithmica 20, 119–135 (1998)

He, X.: On Floor-Plan of Plane Graphs. SIAM J. on Computing 28(6), 2150–2167 (1999)

He, X., Kao, M.-Y., Lu, H.-I.: Linear-Time Succinct Encodings of Planar Graphs via Canonical Orderings. SIAM J. on Discrete Mathematics 12(3), 317–325 (1999)

Kant, G.: Drawing Planar Graphs using the lmc-Ordering. Technical Report RUUCS-92-33, Dep. of Information and Computing Sciences, Utrecht University (1992)

Kant, G.: Drawing Planar Graphs Using the Canonical Ordering. Algorithmica 16(4), 4–32 (1996)

Kant, G.: A More Compact Visibility Representation. Int. J. of Computational Geometry and Applications 7(3), 197–210 (1997)

Kant, G., He, X.: Regular Edge Labeling of 4-Connected Plane Graphs and its Applications in Graph Drawing Problems. Theoretical Computer Science 172(12), 175–193 (1997)

Miura, K., Azuma, M., Nishizeki, T.: Canonical Decomposition, Realizer, Schnyder Labeling and Orderly Spanning Trees of Plane Graphs. Int. J. of Foundations of Computer Science 16(1), 117–141 (2005)

Nakano, S.-I.: Planar Drawings of Plane Graphs. IEICE Transactions on Information and Systems E83-D(3), 384–391 (2000)

Schnyder, W.: Embedding Planar Graphs on the Grid. In: Proc. 1st ACM–SIAM Symp. on Discrete Algorithms (SODA 1990), pp. 138–148 (1990)

Wada, K., Chen, W.: Linear Algorithms for a k-Partition Problem of Planar Graphs. In: Hromkovic, J., Sýkora, O. (eds.) WG 1998. LNCS, vol. 1517, pp. 324– 336. Springer, Heidelberg (1998)