Incidence poset

A graph and its incidence poset

In mathematics, an incidence poset or incidence order is a type of partially ordered set that represents the incidence relation between vertices and edges of an undirected graph. The incidence poset of a graph G has an element for each vertex or edge in G. In this poset, there is an order relation x ≤ y if and only if either x = y or x is a vertex, y is an edge, and x is an endpoint of (incident to) y.

## Contents

* 1 Example
* 2 Properties
* 3 Incidence poset of vertices, edges and faces
* 4 See also
* 5 References

## Example

As an example, a zigzag poset or fence with an odd number of elements, with alternating order relations a < b > c < d... is an incidence poset of a path graph.

## Properties

Every incidence poset of a non-empty graph has height two. Its width equals the number of edges plus the number of acyclic connected components.

Incidence posets have been particularly studied with respect to their order dimension, and its relation to the properties of the underlying graph. The incidence poset of a connected graph G has order dimension at most two if and only if G is a path graph, and has order dimension at most three if and only if G is at most planar (Schnyder's theorem).[1] However, graphs whose incidence posets have order dimension 4 may be dense[2] and may have unbounded chromatic number.[3] Every complete graph on n vertices, and by extension every graph on n vertices, has an incidence poset with order dimension O(log log n).[4] If an incidence poset has high dimension then it must contain copies of the incidence posets of all small trees either as sub-orders or as the duals of sub-orders.[5]

## Incidence poset of vertices, edges and faces

a planar map with its incidence poset of vertices, edges and faces

Given a planar map, a planar graph with a fixed plane embedding, one can look at the incidence poset of vertices, edges and faces. The resulting incidence poset then has height three and is given by the natural incidence relations between vertices, edges, and faces. [6]

For a planar map, the order dimension of their incidence poset is at most four.[7]

## See also

* Line graph, a related construction

## References

1. ↑ Schnyder, W. (1989), "Planar graphs and poset dimension", Order 5 (4): 323–343, doi:10.1007/BF00353652 .
2. ↑ Agnarsson, Geir; Felsner, Stefan; Trotter, William T. (1999), "The maximum number of edges in a graph of bounded dimension, with applications to ring theory", Discrete Mathematics 201 (1–3): 5–19, doi:10.1016/S0012-365X(98)00309-4 .
3. ↑ Trotter, William T.; Wang, Ruidong (2014), "Incidence posets and cover graphs", Order 31 (2): 279–287, doi:10.1007/s11083-013-9301-9 .
4. ↑ Hoşten, Serkan; Morris, Walter D. Jr. (1999), "The order dimension of the complete graph", Discrete Mathematics 201 (1–3): 133–139, doi:10.1016/S0012-365X(98)00315-X .
5. ↑ Brightwell, Graham R.; Trotter, William T. (1994), "Incidence posets of trees in posets of large dimension", Order 11 (2): 159–167, doi:10.1007/BF01108600 .
6. ↑ Felsner, Stefan. "The Order Dimension of Planar Maps Revisited" (in en). SIAM Journal on Discrete Mathematics 28 (3): 1093–1101. doi:10.1137/130945284. ISSN 0895-4801. http://epubs.siam.org/doi/10.1137/130945284.
7. ↑ Brightwell, Graham R.; Trotter, William T.. "The Order Dimension of Planar Maps" (in en). SIAM Journal on Discrete Mathematics 10 (4): 515–528. doi:10.1137/S0895480192238561. ISSN 0895-4801. http://epubs.siam.org/doi/10.1137/S0895480192238561.

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Incidence poset. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Incidence_poset&oldid=4347360"