Can I read On the Rectilinear Crossing Number of Complete Balanced Multipartite Graphs and Layered Graphs on EtoBox?

On the Rectilinear Crossing Number of Complete Balanced Multipartite Graphs and Layered Graphs by Fabila-Monroy, Ruy; Paul, Rosna; Viafara-Chanchi, Jenifer; Weinberger, Alexandra is a scholarly article available to read on EtoBox.

What is On the Rectilinear Crossing Number of Complete Balanced Multipartite Graphs and Layered Graphs about?

A rectilinear drawing of a graph is a drawing of the graph in the plane in which the edges are drawn as straight-line segments. The rectilinear crossing number of a graph is the minimum number of pairs of edges that cross over all rectilinear drawings of the graph. Let $n \ge r$ be positive integers. The graph $K_n^r$, is the complete $r$-partite graph on $n$ vertices, in which every set of the partition has at least $\lfloor n/r \rfloor$ vertices. The layered graph, $L_n^r$, is an $r$-partite graph on $n$ vertices, in which for every $1\le i \le r-1$, all the vertices in the $i$-th partition are adjacent to all the vertices in the $(i+1)$-th partition. In this paper, we give upper bounds on the rectilinear crossing numbers of $K_n^r$ and~$L_n^r$.

Author

Fabila-Monroy, Ruy; Paul, Rosna; Viafara-Chanchi, Jenifer; Weinberger, Alexandra

Published

2024

Language

EN