✦ LIBER ✦

Posets and planar graphs

✍ Scribed by Stefan Felsner; William T. Trotter

Publisher: John Wiley and Sons
Year: 2005
Tongue: English
Weight: 112 KB
Volume: 49
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20081

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Usually dimension should be an integer valued parameter. We introduce a refined version of dimension for graphs, which can assume a value [t − 1 ↕ t], thought to be between t − 1 and t. We have the following two results: (a) a graph is outerplanar if and only if its dimension is at most [2↕3]. This characterization of outerplanar graphs is closely related to the celebrated result of W. Schnyder [16] who proved that a graph is planar if and only if its dimension is at most 3. (b) The largest n for which the dimension of the complete graph K~n~ is at most [t − 1 ↕ t] is the number of antichains in the lattice of all subsets of a set of size t − 2. Accordingly, the refined dimension problem for complete graphs is equivalent to the classical combinatorial problem known as Dedekind's problem. This result extends work of Hoşten and Morris [14]. The main results are enriched by background material, which links to a line of research in extremal graph theory, which was stimulated by a problem posed by G. Agnarsson: Find the maximum number of edges in a graph on n nodes with dimension at most t. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 273–284, 2005

📜 SIMILAR VOLUMES

Planarity and Edge Poset Dimension

✍ Hubert de Fraysseix; Patrice Ossona de Mendez 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 291 KB

Hereditary properties of combinatorial s

Hereditary properties of combinatorial structures: Posets and oriented graphs

✍ József Balogh; Béla Bollobás; Robert Morris 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 247 KB 👁 1 views

## Abstract A hereditary property of combinatorial structures is a collection of structures (e.g., graphs, posets) which is closed under isomorphism, closed under taking induced substructures (e.g., induced subgraphs), and contains arbitrarily large structures. Given a property $\cal {P}$, we write

Reconstruction of Posets with the Same C

Reconstruction of Posets with the Same Comparability Graph

✍ Pierre Ille; Jean-Xavier Rampon 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 221 KB

Given two finite posets P and P$ with the same comparability graph, we show that if |V(P)| 4 and if for all x # V(P), P&x & P$&x, then P &P$. This result leads us to characterize the finite posets P such that for all x # V(P), P&x & P\*&x.

On planar hypohamiltonian graphs

✍ Gábor Wiener; Makoto Araya 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 144 KB

We present a planar hypohamiltonian graph on 42 vertices and (as a corollary) a planar hypotraceable graph on 162 vertices, improving the bounds of Zamfirescu and Zamfirescu and show some other consequences. We also settle the open problem whether there exists a positive integer N, such that for eve

-constructibility of planar graphs

✍ C. M. Mynhardt; I. Broere 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 386 KB

## Abstract In this paper, the concept of the 𝒢‐constructibility of graphs is introduced and investigated with particular reference to planar graphs. It is conjectured that the planar graphs are minimally __N__‐constructible, where __N__ is a finite set of graphs and an infinite set 𝒢 is obtained s

Decomposing a Planar Graph into Degenera

Decomposing a Planar Graph into Degenerate Graphs

✍ C. Thomassen 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 477 KB

We prove the conjecture made by $\mathrm{O}$. V. Borodin in 1976 that the vertex set of any planar graph can be decomposed into two sets such that one of them induces a 3-degenerate graph and the other induces a 2-degenerate graph. that is, a forest. c. 1995 Academic Press. Inc.