Orthogonal drawings and crossing numbers of the Kronecker product of two cycles

DOI10.1016/J.JPDC.2011.11.009MaRDI QIDQ433407zbMATH OpenOpenAlexFDO

Authors Pranava K. Jha, Savitri Devisetty

Publication date 13 July 2012

Published in Journal of Parallel and Distributed Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jpdc.2011.11.009

zbMATH Keywords

Kronecker productgraph algorithmscyclesgraph minorgridsCartesian productcrossing numbervertex partitionorthogonal drawing

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph operations (line graphs, products, etc.) (05C76)

Recommendations

• Geometric drawings of \(K_{n}\) with few crossings
• The crossing numbers of certain Cartesian products
• Some crossing numbers of products of cycles
• scientific article; zbMATH DE number 3954951
• scientific article; zbMATH DE number 2080106
• scientific article; zbMATH DE number 5257395
• Crossing numbers and combinatorial characterization of monotone drawings of \(K_n\)
• scientific article; zbMATH DE number 90572
• scientific article; zbMATH DE number 2073946
• Shellable drawings and the cylindrical crossing number of \(K_n\)

Cites work

• scientific article; zbMATH DE number 1693468 (Why is no real title available?)
• scientific article; zbMATH DE number 2123123 (Why is no real title available?)
• scientific article; zbMATH DE number 139936 (Why is no real title available?)
• scientific article; zbMATH DE number 1550912 (Why is no real title available?)
• scientific article; zbMATH DE number 3446923 (Why is no real title available?)
• A framework for solving VLSI graph layout problems
• An Upper Bound for the Bisection Width of a Diagonal Mesh
• An improved bound for the crossing number of \(C_m\times C_n\): a self-contained proof using mostly combinatorial arguments
• Arrangements, circular arrangements and the crossing number of \(C_{7} \times C_{n}\).
• Bounding the crossing number of a graph in terms of the crossing number of a minor with small maximum degree
• Crossing number is hard for cubic graphs
• Diagonal and toroidal mesh networks
• Doing the twist: diagonal meshes are isomorphic to twisted toroidal meshes
• Embeddings of star graphs into optical meshes without bends
• Improved Approximations of Crossings in Graph Drawings and VLSI Layout Areas
• Independence in direct-product graphs
• Intersection of curves and crossing number of \(C_m\times C_n\) on surfaces
• Isomorphic components of Kronecker product of bipartite graphs
• Kronecker products of paths and cycles: Decomposition, factorization and bi-pancyclicity
• ON PLANARITY OF DIRECT PRODUCT OF MULTIPARTITE COMPLETE GRAPHS
• On the computational complexity of upward and rectilinear planarity testing
• On the crossing numbers of loop networks and generalized Petersen graphs
• On the crossing numbers of products of cycles and graphs of order four
• Perfect r-domination in the Kronecker product of two cycles, with an application to diagonal/toroidal mesh
• Some crossing numbers of products of cycles
• The Categorical Product of Graphs
• The crossing number of \(C(mk;\{1,k\})\)
• The crossing number of \(C_3\times C_n\)
• The crossing number of c₄ × c₄
• The crossing number ofCm �Cn is as conjectured forn ?m(m + 1)
• The crossing numbers of join of the special graph on six vertices with path and cycle
• Universality considerations in VLSI circuits

Cited in

(5)

• Rotation and crossing numbers for join products
• On the crossing number for Kronecker product of a tripartite graph with path
• Cycle Kronecker products that are representable as optimal circulants
• Drawings of \(C_m\times C_n\) with one disjoint family. II
• There is a unique crossing-minimal rectilinear drawing of \(K_{18}\)

This page was built for publication: Orthogonal drawings and crossing numbers of the Kronecker product of two cycles

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