Sequentially embeddable graphs

DOI10.1002/JGT.22524MaRDI QIDQ5066908zbMATH OpenOpenAlexWikidataFDO

Authors Jackson Autry, Christopher O'Neill

Publication date 31 March 2022

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1812.02904

zbMATH Keywords

embedding on the gridplanar graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Abstract: We call a (not necessarily planar) embedding of a graph $G$ in the plane emph{sequential} if its vertices lie in $mathbb{Z}^2$ and the line segments between adjacent vertices contain no interior integer points. In this note, we prove (i) a graph $G$ has a sequential embedding if and only if $G$ is 4-colorable, and (ii) if $G$ is planar, then $G$ has a sequential planar embedding.

Recommendations

• On k-sequential graphs
• scientific article; zbMATH DE number 432759
• Grid embedding of 4-connected plane graphs
• On a straight-line embedding problem of graphs
• Embedding planar graphs in four pages

Cited in

(3)

• scientific article; zbMATH DE number 3843804 (Why is no real title available?)
• scientific article; zbMATH DE number 3859160 (Why is no real title available?)
• Universal sequences of spatial graphs

This page was built for publication: Sequentially embeddable graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5066908)