###
**Böltz, Lucas ; Becker, Benjamin ; Frey, Hannes** (2021)

*Local Construction of Connected Plane Subgraphs in Graphs Satisfying Redundancy and Coexistence. *

In: Procedia Computer Science, 195

doi: 10.1016/j.procs.2021.11.016

Article, Bibliographie

## Abstract

Connected plane graphs enable many local algorithmic solutions for data communication, task coordination and network maintenance in wireless sensor networks, sensor-actuator networks and distributed robotics. We study construction of such graphs by removing edges from a given network graph. We assume redundancy and coexistence, a graph structure which holds in realistic wireless network models with high probability and which assures that a connected plane graph can always be constructed with local edge removal rules. We present a local algorithm to construct such a connected plane graph. We prove algorithm correctness under redundancy and coexistence assumption. Furthermore, we discuss how far redundancy and coexistence could be weakened while still assuring correctness of the algorithm.

Item Type: | Article |
---|---|

Erschienen: | 2021 |

Creators: | Böltz, Lucas ; Becker, Benjamin ; Frey, Hannes |

Type of entry: | Bibliographie |

Title: | Local Construction of Connected Plane Subgraphs in Graphs Satisfying Redundancy and Coexistence |

Language: | English |

Date: | 2021 |

Publisher: | Elsevier |

Journal or Publication Title: | Procedia Computer Science |

Volume of the journal: | 195 |

DOI: | 10.1016/j.procs.2021.11.016 |

Abstract: | Connected plane graphs enable many local algorithmic solutions for data communication, task coordination and network maintenance in wireless sensor networks, sensor-actuator networks and distributed robotics. We study construction of such graphs by removing edges from a given network graph. We assume redundancy and coexistence, a graph structure which holds in realistic wireless network models with high probability and which assures that a connected plane graph can always be constructed with local edge removal rules. We present a local algorithm to construct such a connected plane graph. We prove algorithm correctness under redundancy and coexistence assumption. Furthermore, we discuss how far redundancy and coexistence could be weakened while still assuring correctness of the algorithm. |

Divisions: | 18 Department of Electrical Engineering and Information Technology 18 Department of Electrical Engineering and Information Technology > Institute of Computer Engineering 18 Department of Electrical Engineering and Information Technology > Institute of Computer Engineering > Multimedia Communications |

Date Deposited: | 04 May 2023 08:53 |

Last Modified: | 01 Aug 2023 08:52 |

PPN: | 510057632 |

Export: | |

Suche nach Titel in: | TUfind oder in Google |

Send an inquiry |

**Options (only for editors)**

Show editorial Details |