Orthogonal A-trails of 4-regular graphs embedded in surfaces of low genus (Q1924123): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1006/jctb.1996.0017 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1978437601 / rank | |||
Normal rank |
Revision as of 15:31, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Orthogonal A-trails of 4-regular graphs embedded in surfaces of low genus |
scientific article |
Statements
Orthogonal A-trails of 4-regular graphs embedded in surfaces of low genus (English)
0 references
12 January 1997
0 references
Anton Kotzig has shown that every connected 4-regular plane graph has an A-trail, that is an Euler trail in which any two consecutive edges lie on a common face boundary. We shall characterize the 4-regular plane graphs which contain two orthogonal A-trails, that is to say two A-trails for which no subtrail of length 2 appears in both A-trails. Our proof gives rise to a polynomial algorithm for deciding if two such A-trails exist. We shall also discuss the corresponding problem for graphs in the projective plane and the torus, and the related problem of deciding when a 2-regular digraph contains two orthogonal Euler trails.
0 references
embedding in surfaces
0 references
delta-matroid
0 references
transition system
0 references
A-trail
0 references
projective plane
0 references
torus
0 references
digraph
0 references
orthogonal Euler trails
0 references