×

One-sided weak dominance drawing. (English) Zbl 1422.68186

This paper studies the One-Sided Weak Dominance Drawing (OSWDD) problem from the perspectives of computational complexity and approximability. The authors formalize the problem, show that it is NP-hard and describe a half-approximation algorithm for a special case of the general problem.
The Weak Dominance Drawing problem (WDD) is defined as follows: Given a DAG \(G\), find two topological sorts such that the intersection between them is minimized. WDD is a well-studied problem and there exist several papers in the literature that have studied aspects of this problem. The authors, though, are concerned with the variant called OSWDD.
Both WDD and OSWDD are important problems and arise in a number of practical settings. The authors mention social networks, article citations, web graphs and traffic routing. Another application area would be switch-box routing in VLSI design. In short, the problems considered by the authors are of enormous practical significance.
The paper is extremely well-written and the related work is comprehensive. The authors have taken great pains to flesh out every single detail. The results are easily seen to be correct. The NP-completeness result is somewhat complex, and consists of several steps, and the starting point of their reduction is the One-Sided Crossing Minimization 4-Star problem, which is not exactly a well-known problem. An interesting problem is to see if there is a simple reduction to the OSWDD problem from a standard problem such as 3SAT.
The approximation algorithm developed by the authors is novel. They first establish a dimension-dependent lower bound. While the bound they provide is not useful for dimensions greater than 2, since computing the dimension is itself NP-complete, it is useful when \(d=2\), since we can check for this case in polynomial time. In this case, the authors’ algorithm is a half-approximation algorithm.
The authors have obtained some neat results and present them in an elegant fashion.

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C20 Directed graphs (digraphs), tournaments
05C62 Graph representations (geometric and intersection representations, etc.)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25 Analysis of algorithms and problem complexity
68W25 Approximation algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Trotter, W. T., Combinatorics and Partially Ordered Sets: Dimension Theory (1992), The Johns Hopkins University Press · Zbl 0764.05001
[2] Tamassia, R., Handbook of Graph Drawing and, Visualization (Discrete Mathematics and Its Applications) (2007), Chapman & Hall/CRC
[3] Kornaropoulos, E. M.; Tollis, I. G., Weak dominance drawings for directed acyclic graphs, (Proceedings of the International Symposium on Graph Drawing. Proceedings of the International Symposium on Graph Drawing, Lecture Notes in Comput. Sci., vol. 7704 (2012), Springer International Publishing: Springer International Publishing Berlin, Heidelberg), 559-560
[4] Veloso, R. R.; Cerf, L.; Meira, W.; Zaki, M. J., Reachability queries in very large graphs: a fast refined online search approach, (Proceedings of the 17th International Conference on Extending Database Technology, EDBT 2014 (2014)), 511-522
[5] Anand, A.; Seufert, S.; Bedathur, S.; Weikum, G., Ferrari: flexible and efficient reachability range assignment for graph indexing, (Proceedings of the 2013 IEEE International Conference on Data Engineering (ICDE 2013) (2013)), 1009-1020
[6] Li, L.; Hua, W.; Zhou HD-GDD, X., High dimensional graph dominance drawing approach for reachability query, World Wide Web, 20, 4, 677-696 (2017)
[7] Langley, L. J., Recognition of orders of interval dimension two, Discrete Appl. Math., 60, 257-266 (1995) · Zbl 0823.06003
[8] Yannakakis, M., The complexity of the partial order dimension problem, SIAM J. Algebr. Discrete Methods, 3, 3, 351-358 (1982) · Zbl 0516.06001
[9] Yildirim, H.; Chaoji, V.; Zaki, M. J., GRAIL: a scalable index for reachability queries in very large graphs, VLDB, 21, 4, 509-534 (2012)
[10] Wei, H.; Yu, J. X.; Lu, C.; Jin, R., Reachability querying: an independent permutation labeling approach, VLDB, 27, 1-26 (2014)
[11] Su, J.; Zhu, Q.; Wei, H.; Yu, J. X., Reachability querying: can it be even faster?, IEEE Trans. Knowl. Data Eng., 29, 3, 683-697 (2017)
[12] Kornaropoulos, E. M., Dominance Drawing of Non-Planar Graphs (2012), University of Crete: University of Crete Greece, Master’s thesis
[13] Brandenburg, F. J.; Gleißner, A.; Hofmeier, A., Comparing and aggregating partial orders with Kendall tau distances, Discrete Math. Algorithms Appl., 05, 02, 25 (2013) · Zbl 1294.06002
[14] Muñoz, X.; Unger, W.; Vrt’o, I., One sided crossing minimization is NP-hard for sparse graphs, (Mutzel, P.; Jünger, M.; Leipert, S., Proceedings of the International Symposium on Graph Drawing. Proceedings of the International Symposium on Graph Drawing, Lecture Notes in Comput. Sci., vol. 2265 (2002), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg), 115-123 · Zbl 1054.68598
[15] Eades, P.; Whitesides, S., Drawing graphs in two layers, Theoret. Comput. Sci., 131, 2, 361-374 (1994) · Zbl 0819.68086
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.