Volltext-Downloads (blau) und Frontdoor-Views (grau)
The search result changed since you submitted your search request. Documents might be displayed in a different sort order.
  • search hit 1 of 26
Back to Result List

A Characterization of Radial Graphs

  • A level graph G = (V,E,λ) is a graph with a mapping λ : V → {1,...,k}, k ≥ 1, that partitions the vertex set V as V = V1 ∪...∪ Vk, Vj = λ-1(j), Vi ∩ Vj = ∅ for i ≠ j, such that λ(v) = λ(u) + 1 for each edge (u, v) ∈ E. Thus a level planar graph can be drawn with the vertices of every Vj, 1 ≤ j ≤ k, placed on a horizontal line, representing the level lj , and without crossings of edges, which can be drawn as straight line segments between the levels. Healy, Kuusik and Leipert gave a complete characterization of minimal forbidden subgraphs for level planar graphs (MLNP patterns) for hierarchies [4]. Minimal in terms of deleting an ar- bitrary edge leads to level planarity. A radial graph partitions the vertex set on radii, which can be pictured as concentric circles, instead of levels, lj = (j cos(α), j sin(α)), α ∈ [0,2π), mapped around a shared center, where j, 1 ≤ j ≤ k indicates the concentric circles’ radius. Comparing embeddings of radial graphs with that of level graphs we gain a further possibility to place an edge and eventually avoid edge crossings which we wish to prevent for planarity reasons. This offers a new set of minimal radial non planar subgraphs (MRNP patterns). Some of the MLNP pat- terns can be adopted as MRNP patterns while some turn out to be radial planar. But based on the radial planar MLNP patterns and the use of augmentation we can build additional MRNP patterns that did not occur in the level case. Furthermore we point out a new upper bound for the number of edges of radial planar graphs. It depends on the subgraphs in- duced between two radii. Because of the MRNP patterns these subgraphs can either consist of a forest or a cycle with several branches. Applying the bound we are able to characterize extremal radial planar graphs. Keywords: radial graphs, minimal non-planarity, extremal radial planar

Download full text files

Export metadata

Additional Services

Search Google Scholar

Statistics

frontdoor_oas
Metadaten
Author:Katharina Hammersen
URN:urn:nbn:de:hbz:832-epub-3965
Year of Completion:2013
Document Type:Preprint
Language:English
Date of Publication (online):2013/02/20
Tag:Extremal radial graphs; Minimal non-planarity; Radial graphs
Institutes:Informations-, Medien- und Elektrotechnik (F07) / Fakultät 07 / Institut für Nachrichtentechnik
Dewey Decimal Classification:600 Technik, Medizin, angewandte Wissenschaften / 620 Ingenieurwissenschaften und Maschinenbau
Open Access:Open Access