THE BASIS NUMBER OF 1-PLANAR GRAPHS

Saman Bazargani, Therese Biedl, Prosenjit Bose, Anil Maheshwari, Babak Miraftab · 2024

Read THE BASIS NUMBER OF 1-PLANAR GRAPHS by Saman Bazargani, Therese Biedl, Prosenjit Bose, Anil Maheshwari, Babak Miraftab (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-18595.txt.

Introduction

Saman Bazargani and co-authors study a graph number tied to how loop sets cover a drawing in a 2024 paper. A graph's cycle space can be spanned by a small set of loops, and the basis number caps how many of those loops may share one edge. Flat graphs with no crossings have basis number two at most.

The team asks the same for graphs drawn with at most one crossing per edge. In full, that number can grow without bound. Yet for many named subclasses of such graphs, the team shows the number stays capped. The result sorts which near-flat graphs keep tidy loop bases.

Catalog record

CREATORSaman Bazargani, Therese Biedl, Prosenjit Bose, Anil Maheshwari, Babak Miraftab
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE58 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-18595

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

THE BASIS NUMBER OF 1-PLANAR GRAPHS Saman Bazargani, Therese Biedl, Prosenjit Bose, Anil Maheshwari, Babak Miraftab Abstract Let ℬ \mathcal{B} be a set of Eulerian subgraphs of a graph G G . We say ℬ \mathcal{B} forms a k k -basis if it is a minimum set that generates the cycle space of G G , and any edge of G G lies in at most k k members of ℬ \mathcal{B} . The basis number of a graph G G , denoted by b ⁡ ( G ) b(G) , is the smallest integer such that G G has a k k -basis. A graph is called 1-planar (resp. planar ) if it can be embedded in the plane with at most one crossing (resp. no crossing) per edge. MacLane’s planarity criterion characterizes planar graphs based on their cycle space, stating that a graph is planar if and only if it has a 2 2 -basis. We study here the basis number of 1-planar graphs, demonstrate that it is unbounded in general, and show that it is bounded for many subclasses of 1-planar graphs. \allowdisplaybreaks \DeclareMathOperator 0ptdepth \DeclareMathOperator \tw tw \DeclareMathOperator \dist dist \DeclareMathOperator \diam diam 1 Introduction For any graph G=(V,E) , the cycle space \mathcal{C}(G) of G consists of all Eulerian subgraphs of G . (Detailed definitions are in Section 2 .) A basis of the cycle space consists of a minimum set of Eulerian subgraphs from which we can generate all elements of \mathcal{C}(G) via taking symmetric differences (or equivalently, linear combinations over \mathbb{F}_{2} ). Extensive research has been conducted in the field of cycle basis theory, and a multitude of results have been obtained by various researchers [ 17 , 15 , 27 ] . Notably, it is regarded as a source of matroid theory [ 26 , 29 ] , a branch of mathematics that focuses on linear dependency. The practical applications of cycle basis theory extend to diverse fields, including electric circuit theory [ 10 ] , and chemical structure storage and retrieval systems [ 12 ] . A planar graph is a graph that can be drawn in a plane without any of its edges crossing. A result by MacLane [ 21 ] characterizes planar graphs in terms of their cycle space. Lemma 1.1 (MacLane’s planarity criterion [ 21 ] ) . A graph is planar if and only if there is a basis for its cycle space such that every edge lies in at most two elements of the basis. Schmeichel [ 25 ] introduced a specific term for the property described in MacLane’s planarity criterion: Call a basis \mathcal{B} of the cycle space a k -basis if every edge belongs to at most k members of \mathcal{B} , and let the basis number of G be the smallest k such that G has a k -basis. Then MacLane’s planarity criterion can be phrased equivalently that planar graphs are exactly the graphs with basis number at most 2. Numerous authors have investigated the basis number of other kinds of graphs, and how it changes when doing graph operations. Schmeichel [ 25 ] showed that the basis number can be unbounded, and gave bounds on the basis number of complete graphs, hypercubes and some complete bipartite graphs. Banks and Schmeichel [ 7 ] and later McCall [ 22 ] studied these graph classes further and made the bounds tight. The basis number of specific graphs, such as the Petersen graph, the Heawood graph, and some cage graphs, was discussed by Alsardary and Ali [ 2 ] . As for graph operations, Alsardary [ 1 ] and Alzoubi [ 4 , 5 ] studied Cartesian products of certain graphs of known basis number, Alzoubi and Jaradat [ 18 ] studied lexicographic products, and Jaradat [ 19 ] considered the strong product with a bipartite graph. In this paper, motivated by MacLane’s planarity criterion, we ask what the basis number is for graphs that are not planar, but that are “close to planar” in some sense. To our knowledge, there were no results in this area until now. In very recent research (concurrent with our own paper) it was proved that every graph with genus 1, and in particular, every toroidal graph, has a 3-basis [ 20 ] . We investigate here graphs that generalize planarity in a different way, and specifically, study the basis number of 1 -planar graphs. A graph G is 1 -planar , if it can be drawn such that each edge is crossed at most once. It would be a natural guess to think that they also have small basis number. But as our first main result, we show that this is not the case: for every integer \ell , there exists a 1 -planar graph G with basis number \ell or more, see 4.1 . In fact, this result even holds under further restrictions on the graph, such as bounding the maximum degree, or forbidding two crossings to share vertices. We then turn towards subclasses of 1-planar graphs that do have a bounded basis number. We first show that if (in some 1-planar drawing) the set of edges without crossings forms a connected subgraph, then the basis number is at most 4. With this, we immediately get this bound on the basis number for some frequently studied subclasses such as locally maximal 1-planar graphs, which include the optimal 1-planar graphs (definitions of these will be given below). Pushing the results further, we show that for some subclasses (usually obtained by restricting configurations near crossings further) the basis number is at most 3. Many of our arguments rely on showing that local graph operations, such as contracting and adding an edge, do not change the basis number significantly. As this may be of interest on its own, we group all these results together in Section 3 , before giving the results for 1-planar graphs in Section 4 and concluding with open problems in Section 5 . 2 Preliminaries We refer the readers to [ 11 ] for notation and terminology of the graph theoretical terms and to [ 9 ] for linear algebra notation, and provide here brief refreshers of only the most important (or non-standard) definition. Throughout, let G=(V,E) be a graph with n vertices and m edges. Cycle space. The cycle space of a graph G , denoted by \mathcal{C}(G) , is the collection of all subgraphs of G that have the form C_{1}+\dots+C_{k} where C_{1},\dots,C_{k} are cycles of G and + denotes the symmetric difference. Equivalently, the cycle space of a graph is defined as the set of all Eulerian subgraphs of G , i.e., subgraphs where all vertex-degrees are even. (The empty subgraph is considered to be Eulerian, and is denoted by \emptyset .) The set \mathcal{C}(G) can be viewed as a vector space over the finite field \mathbb{F}_{2} , i.e., addition means taking the symmetric difference, and scaling is permitted only with 0 or 1. We can therefore use standard vector space terminology, such as generating set and basis , also for the cycle space \mathcal{C}(G) . To remind the reader of these terms: We say that a set S=\{v_{1},\dots,v_{s}\} of vectors in a

Read the complete text