How should they be physically connected?
If the distance is not too great and you don't have many machines in your local network (e.g. it's only those 2 Ubuntu hosts), then your option would be to directly connect the 2 Ubuntu hosts to the router via an UTP cable (Ubuntu host 1 is connected to the Router via a cable, Ubuntu host 2 is connected to the Router via a cable as well). By using direct cable connection you'll avoid the higher latencies that WiFi has.
However, if the distance is too great and you have more machines that need a direct connection, then you can use a switch. The switch has to be connected via one of its ports to the router, and then you connect your machines to the other ports of the switch.
How should the IP addresses of the virtual machines be visible to other VMs/hosts?
Configure Public bridge networking for your virtual machines. This will assign them IP addresses in your local network, so you can access them via your host or other virtual machines that are configured in the same way.
See How to configure Public Bridge @ KVM Networking for a detailed guide on how to achieve that.
You can also check this article from VMware which explains what bridging is.
Note: If you want only the VMs to be able to access each other, and not access them from other hosts, you can use Private bridge configuration, which will setup a local network only for the virtual machines, so they will be in a seperate network.