NodeTrix Planarity Testing with Small Clusters.

Di Giacomo, Emilio and Liotta, Giuseppe and Patrignani, Maurizio and Tappini, Alessandra (2017) NodeTrix Planarity Testing with Small Clusters. In: Graph Drawing and Network Visualization. GD 2017, September 25-27 , pp. 479-491(Official URL: https://doi.org/10.1007/978-3-319-73915-1_37).

Full text not available from this repository.

Abstract

We study the NodeTrix planarity testing problem for flat clustered graphs when the maximum size of each cluster is bounded by a constant k. We consider both the case when the sides of the matrices to which the edges are incident are fixed and the case when they can be arbitrarily chosen. We show that NodeTrix planarity testing with fixed sides can be solved in O(k^3k+3/2 n³) time for every flat clustered graph that can be reduced to a partial 2-tree by collapsing its clusters into single vertices. In the general case, NodeTrix planarity testing with fixed sides can be solved in O(n³) time for k=2, but it is NP-complete for any k≥3. NodeTrix planarity testing remains NP-complete also in the free side model when k>4.

Item Type: Conference Paper
Classifications: G Algorithms and Complexity > G.770 Planarity Testing
P Styles > P.120 Circular
P Styles > P.999 Others
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1625

Actions (login required)

View Item View Item