About: Clustered planarity testing revisited

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Clustered planarity testing revisited Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
rdfs:seeAlso	http://link.springer.com/content/pdf/10.1007%2F978-3-662-45803-7_36.pdf
Description	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. Di Battista and Frati 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. 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. Di Battista and Frati 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. (en)
Title	Clustered planarity testing revisited Clustered planarity testing revisited (en)
skos:prefLabel	Clustered planarity testing revisited Clustered planarity testing revisited (en)
skos:notation	RIV/00216208:11320/14:10282839!RIV15-MSM-11320___
http://linked.open...avai/riv/aktivita	I P S
http://linked.open...avai/riv/aktivity	I, P(GEGIG/11/E023), S
http://linked.open...vai/riv/dodaniDat	2015
http://linked.open...aciTvurceVysledku	Kynčl, Jan Fulek, Radoslav
http://linked.open.../riv/druhVysledku	D - Článek ve sborníku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	Univerzita Karlova v Praze / Matematicko-fyzikální fakulta
http://linked.open...dnocenehoVysledku	7590
http://linked.open...ai/riv/idVysledku	RIV/00216208:11320/14:10282839
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	Matroid intersection algorithm; Hanani-Tutte theorem; Clustered planarity (en)
http://linked.open.../riv/klicoveSlovo	Clustered planarity Hanani-Tutte theorem Matroid intersection algorithm
http://linked.open...ontrolniKodProRIV	[5CA8A904C5B4]
http://linked.open...v/mistoKonaniAkce	Würzburg
http://linked.open...i/riv/mistoVydani	Neuveden
http://linked.open...i/riv/nazevZdroje	Graph Drawing
http://linked.open...in/vavai/riv/obor	BA
http://linked.open...ichTvurcuVysledku	2 (xsd:int)
http://linked.open...cetTvurcuVysledku	4 (xsd:int)
http://linked.open...vavai/riv/projekt	Graph Drawings and Representations
http://linked.open...UplatneniVysledku	2014
http://linked.open...iv/tvurceVysledku	Kynčl, Jan Pálvölgyi, Dömötör Fulek, Radoslav Malinović, Igor
http://linked.open...vavai/riv/typAkce	WRD - Světová
http://linked.open.../riv/zahajeniAkce	2014-09-24 (xsd:date)
issn	0302-9743
number of pages	12 (xsd:int)
http://bibframe.org/vocab/doi	10.1007/978-3-662-45803-7_36
http://purl.org/ne...btex#hasPublisher	Springer-Verlag. (Berlin; Heidelberg)
https://schema.org/isbn	978-3-662-45802-0
http://localhost/t...ganizacniJednotka	11320

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 112 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software