Genus Ranges of 4-Regular Rigid Vertex Graphs.

Area of Science:

• Graph Theory
• Combinatorial Topology
• Computational Geometry

Background:

• Rigid vertex graphs possess a fixed cyclic order of incident edges.
• Orientable genus of a graph embedding quantifies the minimal genus of an orientable surface where it can be embedded.
• Understanding genus ranges is crucial for classifying graph embeddings.

Purpose of the Study:

• To determine the possible orientable genus ranges for 4-regular rigid vertex graphs.
• To identify which intervals of integers can be realized as genus ranges.
• To characterize the types of graphs that realize these genus ranges.

Main Methods:

• Investigating cellular embeddings of 4-regular rigid vertex graphs on orientable surfaces.
• Analyzing the properties of genus ranges, which are sets of consecutive integers.
• Developing explicit graph constructions to realize specific genus ranges.

Main Results:

• Genus ranges of 4-regular rigid vertex graphs are sets of consecutive integers.
• For graphs with 2n vertices (n>1), all intervals [a, b] with a < b ≤ n and singletons [h, h] with h ≤ n are realized.
• For graphs with 2n-1 vertices (n≥1), all intervals [a, b] with a < b ≤ n (except [0, n]) and singletons [h, h] with h ≤ n are realized.

Conclusions:

• The study characterizes the complete set of realizable orientable genus ranges for 4-regular rigid vertex graphs.
• Explicit constructions are provided, offering practical examples for theoretical findings.
• This work contributes to the understanding of graph embeddings and their topological properties.