×

zbMATH — the first resource for mathematics

Balanced vertex-orderings of graphs. (English) Zbl 1060.05088
Summary: In this paper we consider the problem of determining a balanced ordering of the vertices of a graph; that is, the neighbors of each vertex \(v\) are as evenly distributed to the left and right of \(v\) as possible. This problem, which has applications in graph drawing for example, is shown to be NP-hard, and remains NP-hard for bipartite simple graphs with maximum degree six. We then describe and analyze a number of methods for determining a balanced vertex-ordering, obtaining optimal orderings for directed acyclic graphs, trees, and graphs with maximum degree three. For undirected graphs, we obtain a 13/8-approximation algorithm. Finally we consider the problem of determining a balanced vertex-ordering of a bipartite graph with a fixed ordering of one bipartition. When only the imbalances of the fixed vertices count, this problem is shown to be NP-hard. On the other hand, we describe an optimal linear time algorithm when the final imbalances of all vertices count. We obtain a linear time algorithm to compute an optimal vertex-ordering of a bipartite graph with one bipartition of constant size.

MSC:
05C85 Graph algorithms (graph-theoretic aspects)
05C10 Planar graphs; geometric and topological aspects of graph theory
68R10 Graph theory (including graph drawing) in computer science
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Berger, B.; Shor, P.W., Tight bounds for the maximum acyclic subgraph problem, J. algorithms, 25, 1-18, (1997) · Zbl 0888.68088
[2] Biedl, T.; Kant, G., A better heuristic for orthogonal graph drawings, Comput. geom., 9, 3, 159-180, (1998) · Zbl 0894.68104
[3] Biedl, T.C.; Kaufmann, M., Area-efficient static and incremental graph drawings, (), 37-52
[4] T. Biedl, T. Chan, Y. Ganjali, M. Hajiaghayi, D.R. Wood, Balanced vertex-orderings of graphs, Tech. Rep. TR-2002-01, School of Computer Science, Carleton University, Ottawa, Canada, 2002. · Zbl 1060.05088
[5] Biedl, T.C.; Madden, B.P.; Tollis, I.G., The three-phase methoda unified approach to orthogonal graph drawing, International J. comp. geometry appl., 10, 6, 553-580, (2000) · Zbl 0970.68186
[6] Blum, M.; Floyd, R.W.; Pratt, V.; Rivest, R.L.; Tarjan, R.E., Time bounds for selection, J. comput. system sci., 7, 448-461, (1973) · Zbl 0278.68033
[7] Brandes, U., Eager st-ordering, (), 247-256 · Zbl 1019.68803
[8] Cheriyan, J.; Reif, J.H., Directed s-t numberings, rubber bands, and testing k-vertex connectivity, Combinatorica, 14, 4, 435-451, (1994) · Zbl 0810.05048
[9] Chrobak, M.; Eppstein, D., Planar orientations with low out-degree and compaction of adjacency matrices, Theoret. comput. sci., 86, 2, 243-266, (1991) · Zbl 0735.68015
[10] Cormen, T.H.; Leiserson, C.E.; Rivest, R.L., Introduction to algorithms, (1990), McGraw-Hill · Zbl 1158.68538
[11] Dietz, P.F.; Sleator, D.D., Two algorithms for maintaining order in a List, (), 365-372
[12] Downey, R.G.; Fellows, M.R., Parameterized complexity, (1999), Springer Berlin · Zbl 0914.68076
[13] de Fraysseix, H.; de Mendez, P.Ossona, Regular orientations, arboricity, and augmentation, (), 111-118
[14] de Fraysseix, H.; Ossona de Mendez, P.; Rosenstiehl, P., Bipolar orientations revisited, Discrete appl. math., 56, 2-3, 157-179, (1995) · Zbl 0830.05023
[15] de Fraysseix, H.; Pach, J.; Pollack, R., How to draw a planar graph on a grid, Combinatorica, 10, 1, 41-51, (1990) · Zbl 0728.05016
[16] Eades, P.; Lin, X.; Smyth, W.F., A fast and effective heuristic for the feedback arc set problem, Inform. process. lett., 47, 6, 319-323, (1993) · Zbl 0787.68078
[17] Eades, P.; Symvonis, A.; Whitesides, S., Three dimensional orthogonal graph drawing algorithms, Discrete appl. math., 103, 55-87, (2000) · Zbl 0958.68135
[18] Ebert, J., st-ordering the vertices of biconnected graphs, Computing, 30, 1, 19-33, (1983) · Zbl 0491.05057
[19] Even, S.; Tarjan, R.E., Computing an st-numbering, Theoret. comput. sci., 2, 3, 339-344, (1976) · Zbl 0341.68029
[20] Even, S.; Tarjan, R.E.; Even, S.; Tarjan, R.E., Corrigendumcomputing an st-numbering, Theoret. comput. sci., Theoret. comput. sci., 4, 1, 123-344, (1997)
[21] Garey, M.R.; Johnson, D.S., Computers and intractabilitya guide to the theory of NP-completeness, (1979), Freeman New York
[22] Kant, G., Drawing planar graphs using the canonical ordering, Algorithmica, 16, 1, 4-32, (1996) · Zbl 0851.68086
[23] Kant, G.; He, X., Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems, Theoret. comput. sci., 172, 1-2, 175-193, (1997) · Zbl 0903.68137
[24] J. Kára, J. Kratochvíl, D.R. Wood, On the complexity of the balanced vertex ordering problem, 2004, Manuscript.
[25] Karp, R.M., Reducibility among combinatorial problems, (), 85-103 · Zbl 0366.68041
[26] Kratochvíl, J.; Tuza, Z., On the complexity of bicoloring clique hypergraphs of graphs, J. algorithms, 45, 1, 40-54, (2002) · Zbl 1030.68066
[27] Lempel, A.; Even, S.; Cederbaum, I., An algorithm for planarity testing of graphs, (), 215-232 · Zbl 0197.50204
[28] Liu, Y.; Morgana, A.; Simeone, B., A linear algorithm for 2-bend embeddings of planar graphs in the two-dimensional grid, Discrete appl. math., 81, 1-3, 69-91, (1998) · Zbl 0912.68153
[29] Maon, Y.; Schieber, B.; Vishkin, U., Parallel ear decomposition search (EDS) and st-numbering in graphs, Theoret. comput. sci., 47, 3, 277-298, (1986) · Zbl 0632.68066
[30] Motwani, R.; Raghavan, P., Randomized algorithms, (1995), Cambridge University Press Cambridge · Zbl 0849.68039
[31] Papakostas, A.; Tollis, I.G., Algorithms for area-efficient orthogonal drawings, Comput. geom., 9, 83-110, (1998) · Zbl 0894.68102
[32] Rosenstiehl, P.; Tarjan, R.E., Rectilinear planar layouts and bipolar orientations of planar graphs, Discrete comput. geom., 1, 4, 343-353, (1986) · Zbl 0607.05027
[33] Schaefer, T.J., The complexity of satisfiability problems, (), 216-226 · Zbl 1282.68143
[34] Tamassia, R.; Tollis, I.G., Planar grid embedding in linear time, IEEE trans. circuits systems, 36, 9, 1230-1234, (1989)
[35] Tarjan, R.E., Two streamlined depth-first search algorithms, Fund. inform., 9, 1, 85-94, (1986) · Zbl 0591.68069
[36] Wood, D.R., Multi-dimensional orthogonal graph drawing with small boxes, (), 311-322 · Zbl 0953.05074
[37] Wood, D.R., Optimal three-dimensional orthogonal graph drawing in the general position model, Theoret. comput. sci., 299, 1-3, 151-178, (2003) · Zbl 1040.68069
[38] Wood, D.R., Minimising the number of bends and volume in three-dimensional orthogonal graph drawings with a diagonal vertex layout, Algorithmica, 39, 3, 235-253, (2004) · Zbl 1094.68107
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.