On the crossing numbers of certain pyramid networks

Gayathri, S. (57197852827) and Rajan, Bharati (22734913500) (2018) On the crossing numbers of certain pyramid networks.

Full text not available from this repository.

Abstract

The investigation on crossing numbers of graphs is a classical and however very difficult problem. It is well known that this problem is NP-complete and the problem of reducing the number of crossings in the graph is studied not only in the graph theory, but also by computer scientists. A good drawing of a graph G is a drawing where the edges are non-self-intersecting and each two edges have at most one point in common, which is either a common end vertex or a crossing. The crossing number of a graph G is the least number of crossings required in any drawing of G. It is one of the successful concepts for measuring non-planarity of graphs. The term crossing comes up because, as it is not difficult to verify, in a drawing with the minimum total number of intersections every intersection is a crossing, rather than tangential. Graph theoretical ideas are highly utilized by computer science applications, especially in research areas of computer science such data mining, image segmentation, clustering, image capturing and networking. Interconnection networks are known to be one of the main limiting factors to computer systems scalability because of the communication and synchronization penalties suffered by applications and their significant overheads in terms of cost, power and performance. The grid-pyramid network has various topological properties. More compact layouts can lead in shorter wire lengths and therefore reducing signal propagation delay as well as lower cost in the implementation process. Two classes of interconnection networks, namely, mesh pyramid networks and Recursive Transpose-Connected Cycles (RTCC) networks are chosen in this paper and crossing number bounds are provided. © 2019 Elsevier B.V., All rights reserved.

Item Type: Article
Subjects:
Divisions: Arts and Science > School of Arts and Science, Chennai > Mathematics
Depositing User: Unnamed user with email techsupport@mosys.org
Last Modified: 11 Dec 2025 06:01
URI: https://vmuir.mosys.org/id/eprint/4691

Actions (login required)

View Item
View Item