An exact approach to upward crossing minimization
Abstract
The upward crossing number problem asks for a drawing of the graph into the plane with the minimum number of edge crossings where the edges are drawn as monotonously increasing curves w.r.t. the y-axis. While there is a large body of work on solving this central graph drawing problem heuristically, we present the first approach to solve the problem to proven optimality. Our approach is based on a reformulation of the problem as a boolean formula that can be iteratively tightened and resolved.
In our experiments, we show the practical applicability and limits of our approach. Furthermore, we can now for the first time evaluate the state-of-the-art heuristics w.r.t. true optimum solutions. This leads to the finding that these algorithms are in general surprisingly far away from the optimum. Finally, we show that we can use our approach as a strong heuristic: even after only one minute of running time, our approach typically gives better solutions than the known heuristics for medium sized instances.
References
[1]
Bachmaier, C., Brandenburg, F. J., Brunner, W., Hübner, F.: A global k-level crossing reduction algorithm. In: Proc. of. WALCOM'10, LNCS 5942 (2010) 70--81
[2]
Bachmaier, C., Brunner, W., Gleissner, A.: Grid sifting: Leveling and crossing reduction. J. Exp. Algorithmics 17 (2012) Art. 1.7, 23p
[3]
Bertolazzi, P., Di Battista, G., Didimo, W.: Quasi-upward planarity. Algorithmica 32(3) (2002) 474--506
[4]
Buchheim, C., Chimani, M., Ebner, D., Gutwenger, C., Jünger, M., Klau, G. W., Mutzel, P., Weiskircher, R.: A branch-and-cut approach to the crossing number problem. Discrete optimization 5(2) (2008) 373--388
[5]
Buchheim, C., Ebner, D., Jünger, M., Klau, G. W., Mutzel, P., Weiskircher, R.: Exact crossing minimization. In Proc. of GD'05, LNCS 3843 (2006) 37--48
[6]
Buchheim, C., Wiegele, A., Zheng, L.: Exact algorithms for the quadratic linear ordering problem. INFORMS J. Comp. 22(1) (2010) 168--177
[7]
Chimani, M., Gutwenger, C., Mutzel, P., Wong, H. M.: Layer-free upward crossing minimization. ACM J. of Experimental Algorithmics 15 (2010)
[8]
Chimani, M., Gutwenger, C., Mutzel, P., Wong, H.: Upward planarization layout. J. of Graph Algortihms and Appl. 15(1) (2011) 127--155
[9]
Chimani, M., Hungerländer, P., Jünger, M., Mutzel, P.: An SDP approach to multi-level crossing minimization. J. Exp. Algorithmics 17 (2012) Art. 3.3, 26p
[10]
Chimani, M., Mutzel, P., Bomze, I.: A new approach to exact crossing minimization. In: Proc. of. ESA'08, LNCS 5193 (2008) 284--296
[11]
Chimani, M., Zeranski, R.: Upward planarity testing via SAT. In: Proc. GD'12, LNCS 7704 (2012) 248--259
[12]
Chimani, M., Zeranski, R.: Upward planarity: A computational study. In: Proc. GD'13, LNCS 8242 (2013)
[13]
Di Battista, G., Garg, A., Liotta, G., Parise, A., Tamassia, R., Tassinari, E., Vargiu, F., Vismara, L.: Drawing directed acyclic graphs: An experimental study. Int. Journal of Computational Geometry and Appl. 10(6) (2000) 623--648
[14]
Eades, P., Wormald, N. C.: Edge crossings in drawings of bipartite graphs. Algorithmica 11(4) 379--403
[15]
Eiglsperger, M., Eppinger, F., Kaufmann, M.: An approach for mixed upward planarization. In: Proc. of WADS'01. LNCS 2125 (2003) 352--364
[16]
Garg, A., Tamassia, R.: On the computational complexity of upward and rectilinear planarity testing. SIAM J. Comp. 31(2) (2002) 601--625
[17]
Gutwenger, C., Klein, K., Mutzel, P.: Planarity testing and optimal edge insertion with embedding constraints. JGAA 12(1) (2008) 73--95
[18]
Healy, P., Kuusik, A.: The vertex-exchange graph: A new concept for multi-level crossing minimisation. In: Proc. GD'99, LNCS 1731 (1999) 205--216
[19]
Hopcroft, J., Tarjan, R.: Efficient planarity testing. J. ACM 21(4) (1974) 549--568
[20]
Jünger, M., Lee, E. K., Mutzel, P., Odenthal, T.: A polyhedral approach to the multi-layer crossing minimization problem. In: Proc. GD'97. LNCS 1353 (1997) 13--24
[21]
Kratochvíl, J.: String graphs. II.: Recognizing string graphs is NP-hard. J. Comb. Theory Ser. B 52(1) (1991) 67--78
[22]
Sugiyama, K., Tagawa, S., Toda, M.: Methods for visual understanding of hierarchical system structures. IEEE Trans. Systems, Man and Cybernetics (1981) 109--125
[23]
Vrt'o, I.: Crossing numbers of graphs: A bibliography. http://www.ifi.savba.sk/~imrich/
[24]
Welzl, E., Di Battista, G., Garg, A., Liotta, G., Tamassia, R., Tassinari, E., Vargiu, F.: An experimental comparison of four graph drawing algorithms. Comp. Geometry 7 (1997) 303--325
Index Terms
- An exact approach to upward crossing minimization
Recommendations
Layer-free upward crossing minimization
An upward drawing of a DAG G is a drawing of G in which all arcs are drawn as curves increasing monotonically in the vertical direction. In this article, we present a new approach for upward crossing minimization, that is, finding an upward drawing of a ...
Optimal k-level planarization and crossing minimization
GD'10: Proceedings of the 18th international conference on Graph drawingAn important step in laying out hierarchical network diagrams is to order the nodes on each level. The usual approach is to minimize the number of edge crossings. This problem is NP-hard even for two layers when the first layer is fixed. Hence, in ...
An SDP approach to multi-level crossing minimization
We present an approach based on semidefinite programs (SDP) to tackle the multi-level crossing minimization problem. We are given a layered graph (i.e., the graph's vertices are assigned to multiple parallel levels) and are asked for an ordering of the ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
January 2014
165 pages
Publisher
Society for Industrial and Applied Mathematics
United States
Publication History
Published: 05 January 2014
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 27Total Downloads
- Downloads (Last 12 months)16
- Downloads (Last 6 weeks)2
Reflects downloads up to 16 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in