descriptionPublicationkeyboard_double_arrow_right Article , Preprint , Conference object 30 Jan 2019Embargo end date: 01 Jan 2016 English Publisher:Springer Science and Business Media LLCJournal:Algorithmica, volume 81, pages 2,484-2,526 (issn: 0178-4617, eissn: 1432-0541,

Authors: Patrizio Angelini; Giordano Da Lozzo;

doi: 10.1007/s00453-018-00541-w , 10.48550/arxiv.1609.09679

arXiv: 1609.09679

handle: 11590/309462 , 11590/350024

Clustered Planarity with Pipes

- Summary
- Subjects
- Metrics

Abstract

We study the version of the C-Planarity problem in which edges connecting the same pair of clusters must be grouped into pipes, which generalizes the Strip Planarity problem. We give algorithms to decide several families of instances for the two variants in which the order of the pipes around each cluster is given as part of the input or can be chosen by the algorithm.

19 pages, 9 figures, extended version of the paper appeared at ISAAC 2016

Related Organizations

Leibniz Association
Germany
Roma Tre University
Italy
University of Tübingen
Germany
Schloss Dagstuhl – Leibniz Center for Informatics
Germany

Keywords

FOS: Computer and information sciences, clustered planarity, SEFE, simultaneous embeddings with fixed edges, Clustered planarity; Fixed parameter tractability; Graph drawing; Simultaneous embeddings with fixed edges; Computer Science (all); Computer Science Applications1707 Computer Vision and Pattern Recognition; Applied Mathematics, FPT, Graph Drawing, G.2.2, 004, Clustered Planarity, Planar graphs; geometric and topological aspects of graph theory, graph drawing, fixed parameter tractability, Graph theory (including graph drawing) in computer science, Graph algorithms (graph-theoretic aspects), Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), 05C10, ddc: ddc:004

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	8
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Top 10%