- Carla Binucci ORCID:orcid.org/0000-0002-5320-91109,
- Emilio Di Giacomo ORCID:orcid.org/0000-0002-9794-19289,
- William J. Lenhart ORCID:orcid.org/0000-0002-8618-244410,
- Giuseppe Liotta ORCID:orcid.org/0000-0002-2886-96949,
- Fabrizio Montecchiani ORCID:orcid.org/0000-0002-0543-89129,
- Martin Nöllenburg ORCID:orcid.org/0000-0003-0454-393711 &
- …
- Antonios Symvonis ORCID:orcid.org/0000-0002-0280-741X12
Part of the book series:Lecture Notes in Computer Science ((LNCS,volume 13764))
Included in the following conference series:
572Accesses
Abstract
Motivated by dynamic graph visualization, we study the problem of representing a graphG in the form of astoryplan, that is, a sequence of frames with the following properties. Each frame is a planar drawing of the subgraph ofG induced by a suitably defined subset of its vertices. Between two consecutive frames, a new vertex appears while some other vertices may disappear, namely those whose incident edges have already been drawn in at least one frame. In a storyplan, each vertex appears and disappears exactly once. For a vertex (edge) visible in a sequence of consecutive frames, the point (curve) representing it does not change throughout the sequence.
Note that the order in which the vertices ofG appear in the sequence of frames is a total order. In theStoryPlan problem, we are given a graph and we want to decide whether there exists a total order of its vertices for which a storyplan exists. We prove that the problem isNP-complete, and complement this hardness with two parameterized algorithms, one in the vertex cover number and one in the feedback edge set number ofG. Also, we prove that partial 3-trees always admit a storyplan, which can be computed in linear time. Finally, we show that the problem remainsNP-complete in the case in which the total order of the vertices is given as part of the input and we have to choose how to draw the frames.
Research partially supported by MIUR grant 20174LF3T8“AHeAD: efficient Algorithms for HArnessing networked Data”, Progetto RICBA21LG"Algoritmi, modelli e sistemi per la rappresentazione visuale di reti”, and the Vienna Science and Technology Fund (WWTF) grant ICT19-035.
This is a preview of subscription content,log in via an institution to check access.
Access this chapter
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
- Chapter
- JPY 3498
- Price includes VAT (Japan)
- eBook
- JPY 9151
- Price includes VAT (Japan)
- Softcover Book
- JPY 11439
- Price includes VAT (Japan)
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Angelini, P., Da Lozzo, G., Neuwirth, D.: Advancements on SEFE and partitioned book embedding problems. Theoret. Comput. Sci.575, 71–89 (2015).https://doi.org/10.1016/j.tcs.2014.11.016
Beck, F., Burch, M., Diehl, S., Weiskopf, D.: The state of the art in visualizing dynamic graphs. In: Borgo, R., Maciejewski, R., Viola, I. (eds.) EuroVis 2014. Eurographics Association (2014).https://doi.org/10.2312/eurovisstar.20141174
Binucci, C., Brandes, U., Di Battista, G., Didimo, W., Gaertler, M., Palladino, P., Patrignani, M., Symvonis, A., Zweig, K.A.: Drawing trees in a streaming model. Inf. Process. Lett.112(11), 418–422 (2012).https://doi.org/10.1016/j.ipl.2012.02.011
Binucci, C., Di Giacomo, E., Lenhart, W.J., Liotta, G., Montecchiani, F., Nöllenburg, M., Symvonis, A.: On the complexity of the storyplan problem. CoRR abs/2209.00453 (2022).https://arxiv.org/abs/2209.00453
Bodlaender, H.L., Kloks, T.: Efficient and constructive algorithms for the pathwidth and treewidth of graphs. J. Algorithms21(2), 358–402 (1996).https://doi.org/10.1006/jagm.1996.0049
Borrazzo, M., Da Lozzo, G., Di Battista, G., Frati, F., Patrignani, M.: Graph stories in small area. J. Graph Algorithms Appl.24(3), 269–292 (2020).https://doi.org/10.7155/jgaa.00530
Da Lozzo, G., Rutter, I.: Planarity of streamed graphs. Theoret. Comput. Sci.799, 1–21 (2019).https://doi.org/10.1016/j.tcs.2019.09.029
Di Giacomo, E., Didimo, W., Liotta, G., Montecchiani, F., Tollis, I.G.: Techniques for edge stratification of complex graph drawings. J. Vis. Lang. Comput.25(4), 533–543 (2014).https://doi.org/10.1016/j.jvlc.2014.05.001
Didimo, W., Liotta, G., Montecchiani, F.: A survey on graph drawing beyond planarity. ACM Comput. Surv.52(1), 1–37 (2019).https://doi.org/10.1145/3301281
Hong, S.-H., Tokuyama, T. (eds.): Beyond Planar Graphs. Springer, Singapore (2020).https://doi.org/10.1007/978-981-15-6533-5
Monien, B., Sudborough, I.H.: Min Cut is NP-complete for edge weighted trees. Theor. Comput. Sci.58, 209–229 (1988).https://doi.org/10.1016/0304-3975(88)90028-X
Robertson, N., Seymour, P.D.: Graph minors. I. Excluding a forest. J. Comb. Theory, Ser. B35(1), 39–61 (1983).https://doi.org/10.1016/0095-8956(83)90079-5
Robertson, N., Seymour, P.: Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms7(3), 309–322 (1986).https://doi.org/10.1016/0196-6774(86)90023-4
Schaefer, M.: Toward a theory of planarity: Hanani-Tutte and planarity variants. J. Graph Algorithms Appl.17(4), 367–440 (2013).https://doi.org/10.7155/jgaa.00298
Skambath, M., Tantau, T.: Offline drawing of dynamic trees: algorithmics and document integration. In: Hu, Y., Nöllenburg, M. (eds.) Graph Drawing and Network Visualization (GD’16). LNCS, vol. 9801, pp. 572–586. Springer (2016).https://doi.org/10.1007/978-3-319-50106-2_44
Vehlow, C., Beck, F., Weiskopf, D.: Visualizing dynamic hierarchies in graph sequences. IEEE Trans. Vis. Comput. Graph.22(10), 2343–2357 (2016).https://doi.org/10.1109/TVCG.2015.2507595
Acknowledgement
Research in this work started at the Bertinoro Workshop on Graph Drawing 2022.
Author information
Authors and Affiliations
Department of Engineering, University of Perugia, Perugia, Italy
Carla Binucci, Emilio Di Giacomo, Giuseppe Liotta & Fabrizio Montecchiani
Department of Computer Science, Williams College, Williamstown, USA
William J. Lenhart
Algorithms and Complexity Group, TU Wien, Vienna, Austria
Martin Nöllenburg
School of Applied Mathematical and Physical Sciences, NTUA, Athens, Greece
Antonios Symvonis
- Carla Binucci
You can also search for this author inPubMed Google Scholar
- Emilio Di Giacomo
You can also search for this author inPubMed Google Scholar
- William J. Lenhart
You can also search for this author inPubMed Google Scholar
- Giuseppe Liotta
You can also search for this author inPubMed Google Scholar
- Fabrizio Montecchiani
You can also search for this author inPubMed Google Scholar
- Martin Nöllenburg
You can also search for this author inPubMed Google Scholar
- Antonios Symvonis
You can also search for this author inPubMed Google Scholar
Corresponding author
Correspondence toEmilio Di Giacomo.
Editor information
Editors and Affiliations
John Cabot University, Rome, Italy
Patrizio Angelini
Kiel University, Kiel, Germany
Reinhard von Hanxleden
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Binucci, C.et al. (2023). On the Complexity of the Storyplan Problem. In: Angelini, P., von Hanxleden, R. (eds) Graph Drawing and Network Visualization. GD 2022. Lecture Notes in Computer Science, vol 13764. Springer, Cham. https://doi.org/10.1007/978-3-031-22203-0_22
Download citation
Published:
Publisher Name:Springer, Cham
Print ISBN:978-3-031-22202-3
Online ISBN:978-3-031-22203-0
eBook Packages:Computer ScienceComputer Science (R0)
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative