Clustered planarity testing revisited
type: Item
instance of: scholarly article
title: Clustered planarity testing revisited
zbMATH Open document ID: 1327.05076
author: Radoslav Fulek
author: Jan Kynčl
author: Igor Malinović
author: Dömötör Pálvölgyi
published in: The Electronic Journal of Combinatorics
publication date: 2015-11-26T00:00:00Z
full work available at URL: v22i4p24
review text: Summary: The Hanani-Tutte theorem is a classical result proved for the first time in the 1930s that characterizes planar graphs as graphs that admit a drawing in the plane in which every pair of edges not sharing a vertex cross an even number of times. We generalize this result to clustered graphs with two disjoint clusters, and show that a straightforward extension to flat clustered graphs with three or more disjoint clusters is not possible. For general clustered graphs we show a variant of the Hanani-Tutte theorem in the case when each cluster induces a connected subgraph. \textit{G. Di Battista} and \textit{F. Frati} [J. Graph Algorithms Appl. 13, No. 3, 349--378 (2009; Zbl 1184.68355)] proved that clustered planarity of embedded clustered graphs whose every face is incident with at most five vertices can be tested in polynomial time. We give a new and short proof of this result, using the matroid intersection algorithm.
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 15A06
Mathematics Subject Classification ID: 05B35
zbMATH DE Number: 6513825
zbMATH Keywords: graph planarity
zbMATH Keywords: clustered planarity
zbMATH Keywords: Hanani-Tutte theorem
zbMATH Keywords: matroid intersection algorithm
MaRDI profile type: Publication
cites work: Strip Planarity Testing
cites work: Q4232783
cites work: Bounds for generalized thrackles
cites work: Upward Planarity Testing: A Computational Study
cites work: C-Planarity of C-Connected Clustered Graphs
cites work: Clustering Cycles into Cycles of Clusters
cites work: Improved Bounds for Matroid Partition and Intersection Algorithms
cites work: Efficient C-Planarity Testing for Embedded Flat Clustered Graphs with Small Faces
cites work: Q4414632
cites work: Planarity for clustered graphs
cites work: TRÉMAUX TREES AND PLANARITY
cites work: A characterization of planar graphs by Trémaux orders
cites work: Towards the Hanani-Tutte Theorem for Clustered Graphs
cites work: Clustered Planarity Testing Revisited
cites work: Hanani–Tutte, Monotone Drawings, and Level-Planarity
cites work: Powers of tensors and fast matrix multiplication
cites work: Q4422278
cites work: Practical Experience with Hanani-Tutte for Testing c-Planarity
cites work: Efficient Planarity Testing
cites work: A generalization of the fast LUP matrix decomposition algorithm and applications
cites work: An algorithmic study of switch graphs
cites work: Matroid intersection algorithms
cites work: Hierarchical planarity testing algorithms
cites work: Q5390304
cites work: Which crossing number is it anyway?
cites work: Towards an implementation of the 3D visibility skeleton
cites work: Strong Hanani–Tutte on the Projective Plane
cites work: Removing even crossings
cites work: Removing even crossings on surfaces
cites work: Hanani-Tutte and Related Results
cites work: Toward a theory of planarity: Hanani-Tutte and planarity variants
cites work: Toward a theory of crossing numbers
cites work: Solving sparse linear equations over finite fields
cites work: Multiplying matrices faster than coppersmith-winograd
description: scientific article; zbMATH DE number 6513825